Pagini recente » Cod sursa (job #1799200) | Cod sursa (job #194763) | Cod sursa (job #231887) | Cod sursa (job #794579) | Cod sursa (job #237566)
Cod sursa(job #237566)
#include <stdio.h>
#include <string.h>
#define Nmax 228
int c[Nmax][Nmax], f[Nmax][Nmax];
int q[Nmax], t[Nmax], v[Nmax],n;
int bfs()
{
memset(t,0,sizeof(t));
memset(v,0,sizeof(v));
v[0] = 1;
int st=0, dr=1, nod;
q[1] = 0;
while(st<dr)
{
nod = q[++st];
for (int i=1;i<=n;++i) if (v[i] == 0)
if (f[nod][i] < c[nod][i])
{
v[i] = 1;
t[i] = nod;
q[++dr] = i;
}
}
if (v[n] == 0) return 0;
return 1;
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d", &n);
int x,y, rec=n, tmp=0;
for (int i=1;i<=n;++i)
{
scanf("%d%d", &x,&y);
c[0][i] = x;
c[n+i][2*n+1] = y;
for (int j=1;j<=n;++j) if (j != i) c[i][n+j] = 1;
}
n = 2*n+1;
while (bfs())
{
int add = 123456789;
for (int nod = n;nod;nod=t[nod])
if (c[t[nod]][nod]-f[t[nod]][nod] < add) add = c[t[nod]][nod]-f[t[nod]][nod];
for (int nod = n;nod;nod=t[nod])
{
f[t[nod]][nod] += add;
f[nod][t[nod]] -= add;
}
tmp += add;
}
printf("%d\n", tmp);
for (int i=1;i<=rec;++i)
for (int j=rec+1;j<=n;++j)
if (f[i][j]) printf("%d %d\n",i,j-rec);
/*
for (int i=0;i<=n;++i)
for (int j=0;j<=n;++j)
if (c[i][j]) printf("%d %d -> %d\n", i,j,c[i][j]);
*/
return 0;
}