Cod sursa(job #392520)

Utilizator ConsstantinTabacu Raul Consstantin Data 7 februarie 2010 17:28:43
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#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;}