Pagini recente » Cod sursa (job #2800395) | Cod sursa (job #2844058) | Cod sursa (job #80917) | Cod sursa (job #2372824) | Cod sursa (job #392520)
Cod sursa(job #392520)
#include<stdio.h>
#define dim 204
#include<string.h>
int c[ dim ][ dim ],t[ dim ],q[ dim ],i,j,k,l,m,n,a,b,Min,flux;
int bfs(){
int p = 1,u = 1,i,x;
for(i = 0;i<=2*n+1;i++)
t[i] = -2;
q[1] = 0;
t[0] = -1;
while(p <= u )
{x = q[p];
for( i = 0; i <= 2*n+1;i++)
if(c[x][i] > 0 && (t[i] ==-2))
{t[i] = x;
q[++u] = i;
if(i == 2*n+1)return 1;
}
p++;
}
return 0;
}
int main(){
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
for(i = 1 ; i <= n ; ++i)
for( j = 1;j <= n ; ++j)
if(i!=j)
c[i][n+j] = 1;
for(i = 1 ; i <= n ;i++)
{scanf("%d %d",&a,&b);
c[0][i] = a;
c[i+n][2*n+1] = b;
m += a;}
while(bfs()){
Min = 1 << 30;
for( i = 2 * n + 1;t[i] != -1; i = t[i])
if(c[t[i]][i] < Min )
Min = c[t[i]][i];
for(i = 2 * n + 1;t[i] != -1; i = t[i])
{c[t[i]][i] -= Min;
c[i][t[i]] += Min;
}
}
printf("%d\n",m);
for (int i=1;i<=n;i++)
for (int j=n+1;j<=2*n;j++)
if (c[i][j]==0 && i!=j-n)
printf("%d %d\n", i, j-n);
return 0;}