Cod sursa(job #270521)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 4 martie 2009 09:20:07
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#include<string.h>
#define N 205
int n,s,d,m;
int c[N][N],f[N][N],t[N],flux;
void citire()
{
	int x,y,j;
	for(int i=1; i<=n; i++)
	{
		scanf("%d%d",&x,&y);
		c[0][i]=x;
		c[i+n][d]=y;
		m+=x;
		for(j=1; j<=n; j++)
		{
			if(j==i)
				continue;
			c[i][j+n]=1;
		}
	}
}
bool bfs()
{
	int p,u,nod,i,q[N];
	memset(t,0xff,sizeof(t));
	p=u=0;
	q[0]=s;
	t[s]=-1;
	for(; p<=u; p++)
	{
		nod=q[p];
		for(i=0; i<=d; i++)
		{
			if(t[i]==-1 && c[nod][i]>f[nod][i])
			{
				q[++u]=i;
				t[i]=nod;
				if(i==d)
					return true;
			}
		}
	}
	return false;
}
int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%d",&n);
	d=(n<<1)+1;
	citire();
	int i,j;
	while(bfs())
	{
		i=d;
		while(i)
		{
			f[t[i]][i]++;
			f[i][t[i]]--;
			i=t[i];
		}
	}
	printf("%d\n",m);
	for(i=1; i<=n; i++)
	{
		for(j=n+1; j<d; j++)
		{
			if(f[i][j]>0)
				printf("%d %d\n",i,j-n);
		}
	}
	return 0;
}