Pagini recente » Arhiva de probleme | Cod sursa (job #674890) | Cod sursa (job #924531) | Cod sursa (job #2582837) | Cod sursa (job #1205656)
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
const int NMAX = 200, SRC = 0, INF = 2e9;
int n, DEST, cap[NMAX + 5][NMAX + 5], flow[NMAX + 5][NMAX + 5], dad[NMAX + 5];
bool vis[NMAX + 5];
queue <int> q;
bool bfs() {
int i, node;
memset(vis, 0, sizeof(vis));
memset(dad, 0, sizeof(dad));
while(!q.empty())
q.pop();
vis[SRC] = 0;
for(i = 1; i <= n; ++ i)
if(cap[SRC][i] > flow[SRC][i]) {
q.push(i);
vis[i] = 1;
dad[i] = SRC;
}
while(!q.empty()) {
node = q.front();
q.pop();
if(node <= n) {
for(i = n + 1; i <= DEST; ++ i)
if(i - n != node && cap[node][i] > flow[node][i] && !vis[i]) {
dad[i] = node;
vis[i] = 1;
q.push(i);
}
}
else {
if(cap[node][DEST] > flow[node][DEST] && !vis[DEST]) {
dad[DEST] = node;
vis[DEST] = 1;
}
for(i = 1; i <= n; ++ i)
if(i != node - n && cap[node][i] > flow[node][i] && !vis[i]) {
dad[i] = node;
vis[i] = node;
q.push(i);
}
}
}
if(vis[DEST])
return 1;
return 0;
}
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
int nEdge, j, i, in, node, out, minFlow;
scanf("%d", &n);
DEST = 2 * n + 1;
nEdge = 0;
for(i = 1; i <= n; ++ i) {
scanf("%d%d", &in, &out);
nEdge += in + out;
cap[SRC][i] = in;
for(j = 1; j <= n; ++ j)
if(i != j)
cap[i][j + n] = 1;
cap[i + n][DEST] = out;
}
while(bfs()) {
for(i = n + 1; i < DEST; ++ i)
if(vis[i]) {
dad[DEST] = i;
minFlow = INF;
node = DEST;
while(node != SRC) {
minFlow = min(minFlow, cap[dad[node]][node] - flow[dad[node]][node]);
node = dad[node];
}
node = DEST;
while(node != SRC) {
flow[dad[node]][node] += minFlow;
flow[node][dad[node]] -= minFlow;
node = dad[node];
}
}
}
printf("%d\n", nEdge / 2);
for(i = 1; i <= n; ++ i)
for(j = 1; j <= n; ++ j)
if(i != j && flow[i][j + n] == 1)
printf("%d %d\n", i, j);
return 0;
}