Cod sursa(job #220478)

Utilizator ilincaSorescu Ilinca ilinca Data 10 noiembrie 2008 23:25:40
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
#include <string.h>

#define maxn 125
#define pmax 2*maxn
#define pr(x) fprintf(stderr,#x" = %d\n",x)


int n, s, d, c [pmax] [pmax], f [pmax] [pmax], prev [pmax], q [pmax*pmax];


void scan ()
{
	int i, j, x, y;
	scanf ("%d", &n);
	d=2*n+1;
	for (i=1; i<=n; ++i)
	{
		scanf ("%d%d", &x, &y);
		c [s] [i]=x;
		c [n+i] [d]=y;
		for (j=n+i+1; j<d; ++j)
			c [i] [j]=c [j-n] [n+i]=1;
	}
}

bool cf ()
{
	int p, u, i;
	memset (prev, -1, sizeof (prev));
	p=u=1;
	q [p]=s;
	prev [0]=0;
	while (p <= u)
	{
		for (i=0; i<=d; ++i)
		{
			if ((c [q [p]] [i] > f [q [p]] [i]) && prev [i] == -1)
			{
				prev [i]=q [p];
				q [++u]=i;
				if (i == d)
					return 1;
			}
		}
		++p;
	}
	return 0;
}

void flux ()
{
	int i;
	while (cf ())
	{
		for (i=d; prev [i] != s; i=prev [i])
		{
			--f [i] [prev [i]];
			++f [prev [i]] [i];
		}
		--f [i] [0];
		++f [0] [i];
	}
}

void print ()
{
	int i, j, w=0, x [pmax*pmax], y [pmax*pmax];
	x [0]=0;
	for (i=1; i<=n; ++i)
		for (j=n+1; j<d; ++j)
			if (f [i] [j])
			{
				++w;
				x [++x [0]]=i;
				y [x [0]]=j-n;
			}
	printf ("%d\n", w);
	for (i=1; i<=x [0]; ++i)
		printf ("%d %d\n", x [i], y [i]);
}

int main ()
{
	freopen ("harta.in", "r", stdin);
	freopen ("harta.out", "w", stdout);
	scan ();	
	flux ();
	print ();
	return 0;
}