Pagini recente » Cod sursa (job #935805) | Cod sursa (job #263386) | Cod sursa (job #1259806) | Cod sursa (job #1591517) | Cod sursa (job #331208)
Cod sursa(job #331208)
#include <cstdio>
#include <cstring>
#include <queue>
#define dim 256
using namespace std;
int n, c[dim][dim], ct=0, p[dim], f=0;
queue<int> q;
int bfs() {
int nod, i, viz[dim];
while (!q.empty()) q.pop();
memset(viz, 0, sizeof(viz));
q.push(0);
viz[0]=1;
while (!q.empty()) {
nod=q.front();
q.pop();
if (nod==2*n+1) continue;
for (i=0; i<=2*n+1; ++i)
if (i!=nod && c[nod][i] && !viz[i]) {
viz[i]=1;
p[i]=nod;
q.push(i);
}
}
return viz[2*n+1];
}
int main() {
int i, j, in, out, fm;
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d\n", &n);
for (i=1; i<=n; ++i) {
scanf("%d %d\n", &in, &out);
ct+=in;
c[0][i]=in;
c[i+n][2*n+1]=out;
}
for (i=1; i<=n; ++i)
for (j=n+1; j<=2*n; ++j)
if (i!=j-n) c[i][j]=1;
for (; bfs(); )
for (i=n+1; i<=2*n; ++i)
if (c[i][2*n+1]) {
p[2*n+1]=i;
fm=1<<30;
for (j=2*n+1; j; j=p[j])
if (c[p[j]][j]<fm) fm=c[p[j]][j];
if (!fm) continue;
for (j=2*n+1; j; j=p[j]) {
c[p[j]][j]-=fm;
c[j][p[j]]+=fm;
}
f+=fm;
}
printf("%d\n", ct);
for (i=1; i<=n; ++i)
for (j=n+1; j<=2*n; ++j)
if (!c[i][j] && i!=j-n) printf("%d %d\n", i, j-n);
return 0;
}