Cod sursa(job #79544)

Utilizator peanutzAndrei Homorodean peanutz Data 23 august 2007 00:44:47
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <string.h>

#define NMAX 210
#define INFI 0x3f3f3f3f

int n;
int in[NMAX], out[NMAX];
int source, sink;
int c[NMAX][NMAX];

void read()
{
	int i;
	scanf("%d", &n);
	for(i = 1; i <= n; ++i)
		scanf("%d%d", out+i, in+i);
}

void init()
{
	int i, j;
	source = 0, sink = 2*n+1;

	for(i = 1; i <= n; ++i)
		c[source][i] = out[i], c[i+n][sink] = in[i];

	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			if(i != j)
				++c[i][j+n];
}

#define MIN(a, b) ((a) < (b)) ? (a) : (b)

int t[NMAX];

int bf()
{
	int inc, sf;
	int q[NMAX], viz[NMAX];
	int i, x;

	memset(viz, 0, sizeof(viz));
	inc = sf = 1;
	q[1] = source;
	viz[source] = 1;

	while(inc <= sf)
	{
		x = q[inc++];

		for(i = source; i <= sink; ++i)
			if(c[x][i] && !viz[i])
			{
				++viz[i];
				q[++sf] = i;
				t[i] = x;

				if(i == sink)
					return 1;
			}
	}
	return 0;
}

void solve()
{
	int i;
	while(bf())
	{
		for(i = sink; i != source; i = t[i])
			++c[i][t[i]], --c[t[i]][i];
	}
}

void print()
{
	printf("           \n");

	int nr = 0, i, j;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			if(i != j && !c[i][j+n])
				++nr, printf("%d %d\n", i, j);

	fseek(stdout, 0, SEEK_SET);
	printf("%d", nr);
}

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

	read();

	init();

	solve();

	print();

	return 0;
}