Cod sursa(job #184821)

Utilizator razvi9Jurca Razvan razvi9 Data 24 aprilie 2008 12:57:02
Problema Taramul Nicaieri Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 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;
}
inline void flux()
{
	while(bf())
	{
		x=2*n+1;
		while(x!=0)
		{
			f[T[x]][x]++;
			f[x][T[x]]--;
			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;
}