Cod sursa(job #219403)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 6 noiembrie 2008 19:36:56
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <string.h>
const int INF=0x3f3f;
int n, c[220][220], prec[220], flux[220][220], f;

void flux_maxim(int s, int d);
bool bf(int s, int d);
int min(int a, int b);

int main()
{
	int i, j, x, y, cont=0;
	freopen("harta.in", "r", stdin);
	freopen("harta.out", "w", stdout);
	scanf("%d", &n);
	for (i=1; i<=n; i++)
	{
		scanf("%d%d", &x, &y);
		c[0][i]=x;
		c[i+n][2*n+1]=y;
		for (j=n+1; j<=2*n; j++)
			c[i][j]=1;
		c[i][i+n]=0;
	}//for i
	flux_maxim(0, 2*n+1);
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (flux[i][j+n])
				++cont;
	printf("%d\n", cont);
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (flux[i][j+n])	
				printf("%d %d\n", i, j);
	return 0;
}//main

void flux_maxim(int s, int d)
{
	int i, minim, f;
	f=0;
	while (bf(s, d))
	{
		minim=INF;
		i=d;
		while (i!=s)
		{
			minim=min(minim, c[prec[i]][i]-flux[prec[i]][i]);
			i=prec[i];
		}//while
		i=d;
		while (i!=s)
		{
			flux[prec[i]][i]+=minim;
			flux[i][prec[i]]-=minim;
			i=prec[i];
		}//while
		f+=minim;
	}//while
}//flux_maxim

bool bf(int s, int d)
{
	int coada[220], p=0, u=0, i, x;
	memset(prec, -1, sizeof(prec));
	coada[u]=s;
	prec[s]=-2;
	while (p<=u)
	{
		x=coada[p++];
		for (i=0; i<=2*n+1; i++)
			if ((prec[i]==-1)&&(c[x][i]>flux[x][i]))
		  {
				prec[i]=x;
				coada[++u]=i;
				if (i==d)
					return 1;
			}//if
	}//while
	return 0;
}//bfs

int min(int a, int b)
{
	if (a<b)
		return a;
	return b;
}//min