Pagini recente » Cod sursa (job #534287) | Cod sursa (job #1370477) | Cod sursa (job #2573051) | Cod sursa (job #1358235) | Cod sursa (job #219403)
Cod sursa(job #219403)
#include <stdio.h>
#include <string.h>
const int INF=0x3f3f;
int n, c[220][220], prec[220], flux[220][220], f;
void flux_maxim(int s, int d);
bool bf(int s, int d);
int min(int a, int b);
int main()
{
int i, j, x, y, cont=0;
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &n);
for (i=1; i<=n; i++)
{
scanf("%d%d", &x, &y);
c[0][i]=x;
c[i+n][2*n+1]=y;
for (j=n+1; j<=2*n; j++)
c[i][j]=1;
c[i][i+n]=0;
}//for i
flux_maxim(0, 2*n+1);
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (flux[i][j+n])
++cont;
printf("%d\n", cont);
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (flux[i][j+n])
printf("%d %d\n", i, j);
return 0;
}//main
void flux_maxim(int s, int d)
{
int i, minim, f;
f=0;
while (bf(s, d))
{
minim=INF;
i=d;
while (i!=s)
{
minim=min(minim, c[prec[i]][i]-flux[prec[i]][i]);
i=prec[i];
}//while
i=d;
while (i!=s)
{
flux[prec[i]][i]+=minim;
flux[i][prec[i]]-=minim;
i=prec[i];
}//while
f+=minim;
}//while
}//flux_maxim
bool bf(int s, int d)
{
int coada[220], p=0, u=0, i, x;
memset(prec, -1, sizeof(prec));
coada[u]=s;
prec[s]=-2;
while (p<=u)
{
x=coada[p++];
for (i=0; i<=2*n+1; i++)
if ((prec[i]==-1)&&(c[x][i]>flux[x][i]))
{
prec[i]=x;
coada[++u]=i;
if (i==d)
return 1;
}//if
}//while
return 0;
}//bfs
int min(int a, int b)
{
if (a<b)
return a;
return b;
}//min