Cod sursa(job #183148)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 21 aprilie 2008 19:28:08
Problema Taramul Nicaieri Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <string.h>

int n, c[201][201], source, sink, t[202], f[202][202];

int min(int x, int y) { return x < y ? x : y; }

int BF()
{
	int i, q[202], p, u;
	memset(t,0,sizeof(t));

	q[1] = source; p = u = 1;
	while (p <= u)
	{
		for (i = 1; i <= n + 1; i++)
			if (c[q[p]][i] - f[q[p]][i] > 0 && !t[i])
			{
				q[++u] = i;
				t[i] = q[p];
				if (i == sink) return 1;
			}
		p++;
	}
	return 0;
}



void flux()
{
	int i, j, r, ok = 0;
	while (BF())
	{
		r = 30000;
		i = sink;
		while (i != source)
		{
			r = min(r,c[t[i]][i] - f[t[i]][i]);
			i = t[i];
		}

		i = sink;
		while (i != source)
		{
			f[t[i]][i] += r;
			f[i][t[i]] -= r;
			i = t[i];
		}
	}

	for (i = 1; i <= n / 2; i++)
		for (j = n / 2 + 1; j <= n; j++)
			if (f[i][j] == 1) printf("%d %d\n",i,j-n/2);		
}






int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);

	int i, j, x, y, s = 0;	

	scanf("%d",&n);
	source = 0;
	sink = 2 * n + 1;

	for (i = 1; i <= n; i++)
	{
		scanf("%d %d", &x, &y);
		c[source][i] = x;
		c[i + n][sink] = y;	
		s += x;
	}
	printf("%d\n",s);	

	for (i = 1; i <= n; i++)
	{
		for (j = n + 1; j <= 2 * n; j++) c[i][j] = 1;
		c[i][i + n] = 0;
	}
	n *= 2;

	flux();
	return 0;
}