Cod sursa(job #184832)

Utilizator razvi9Jurca Razvan razvi9 Data 24 aprilie 2008 13:04:08
Problema Taramul Nicaieri Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<cstdio>
#include<cstring>
int a[202][202],f[202][202],T[202],l[300],i,n,m,x,y,j;
inline int bf()
{
	int st=0,dr=0;
	l[0]=0;
	memset(T,0,sizeof(T));
	while(st<=dr)
	{
		x=l[st];
		for(i=1;i<=2*n+1;i++)
			if(a[x][i]-f[x][i]>0 && !T[i])
			{
				T[i]=x;
				l[++dr]=i;
				if(i==2*n+1) return 1;
			}
		++st;
	}
	return 0;
}
#define min(a,b) (a)<(b)?(a):(b)
inline void flux()
{
	int r;
	while(bf())
	{
		for(i=1;i<=2*n;i++)
			if(T[i] && a[i][2*n+1]-f[i][2*n+1]>=0)
			{
				x=i;
				r=a[i][2*n+1]-f[i][2*n+1];
				while(x!=0 && r)
				{
					r=min(r,a[T[x]][x]-f[T[x]][x]);
					x=T[x];
				}
				if(!r) continue;
				x=i;
				f[i][2*n+1]+=r;
				f[2*n+1][i]-=r;
				while(x!=0)
				{
					f[T[x]][x]+=r;
					f[x][T[x]]-=r;
					x=T[x];
				}
			}
	}
	for(i=1;i<=n;i++)
		for(j=n+1;j<=2*n;j++)
			if(i!=j-n && f[i][j]==1)
				printf("%d %d\n",i,j-n);
}
int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&x,&y);
		a[0][i]=x;
		a[n+i][2*n+1]=y;
		m+=x;
	}
	printf("%d\n",m);
	for(i=1;i<=n;i++)
		for(j=n+1;j<=2*n;j++)
			if(i!=j-n)
				a[i][j]=1;
	flux();
	fclose(stdout);
	return 0;
}