Cod sursa(job #539943)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 23 februarie 2011 15:52:01
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 210
#define inf 1<<30

int c[nmax][nmax], f[nmax][nmax], u[nmax], t[nmax], q[nmax], fm, n, sol;
vector <int> g[nmax];

int min(int a, int b)
{
	if (a>b) a=b;
	return a;
}

int bf()
{
	int i, y, j, h=1, x, nod;
	for (i=0; i<=2*n+1; i++) u[i]=0;
	q[1]=0;
	u[0]=1;
	for (y=1; y<=h; y++)
	{
		i=q[y];
		for (j=0; j<g[i].size(); j++)
		{
			nod=g[i][j];
			if (!u[nod])
				if (c[i][nod]!=f[i][nod])
				{
					u[nod]=1;
					q[++h]=nod;
					t[nod]=i;
					if (nod==2*n+1) return 1;
				}
		}
	}
	return 0;
}

int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%d",&n);
	int i, j, x, y, nod;
	for (i=1; i<=n; i++) 
	{
		scanf("%d %d",&x, &y);
		g[0].push_back(i);
		g[i].push_back(0);
		g[n+i].push_back(2*n+1);
		g[2*n+1].push_back(n+i);
		c[0][i]=x;
		c[n+i][2*n+1]=y;
		for (j=1; j<=n; j++)
			if (i!=j) 
			{
				g[i].push_back(n+j);
				g[n+j].push_back(i);
				c[i][n+j]=1;
			}
	}
	while (bf())
	{
		nod=2*n+1;
		fm=inf;
		while (nod)
		{
			fm=min(fm, c[t[nod]][nod]-f[t[nod]][nod]);
			nod=t[nod];
		}
		nod=2*n+1;
		while (nod)
		{
			f[t[nod]][nod]+=fm;
			f[nod][t[nod]]-=fm;
			nod=t[nod];
		}
	}
	for (i=1; i<=n; i++)
		for (j=0; j<g[i].size(); j++)
		{ 
			nod=g[i][j];
			if (c[i][nod]==f[i][nod] && nod) sol++;
		}
	printf("%d\n",sol);
	for (i=1; i<=n; i++)
		for (j=0; j<g[i].size(); j++)
		{ 
			nod=g[i][j];
			if (c[i][nod]==f[i][nod] && nod) printf("%d %d\n",i,nod-n);
		}
}