Cod sursa(job #387265)

Utilizator loginLogin Iustin Anca login Data 27 ianuarie 2010 10:48:53
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
# include <fstream>
# include <iostream>
# include <cstdio>
using namespace std;
int a[203][203], n, m, in[103], out[103], t[103],fm;

void read ()
{
	ifstream fin ("harta.in");
	fin>>n;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (i!=j)
				a[i][n+j]=1;
	for (int i=1;i<=n;i++)
	{
		fin>>out[i]>>in[i];
		a[0][i]=out[i];
		a[n+i][2*n+1]=in[i];
		m+=out[i];
	}
}

int bfs (int s, int d)
{
	int c[203], st, dr, k;
	for (int i=0;i<=2*n+1;i++)
		t[i]=-2;
	st=dr=1;
	c[st]=s;
	t[s]=-1;
	while (st<=dr)
	{
		k=c[st++];
		for (int i=0;i<=2*n+1;i++)
			if (a[k][i]>0 && t[i]==-2)
			{
				t[i]=k;
				c[++dr]=i;
				if (i==d)
					return 1;
			}
	}
	return 0;
}

void EK ()
{
	int cmin;
	while (bfs(0, 2*n+1))
	{
		cmin=1000000000;
		for (int i=2*n+1;t[i]!=-1;i=t[i])
			if (cmin>a[t[i]][i])
				cmin=a[t[i]][i];
		for (int i=2*n+1;t[i]!=-1;i=t[i])
		{
			a[t[i]][i]-=cmin;
			a[i][t[i]]+=cmin;
		}
		fm+=cmin;
	}
}

void write ()
{
	freopen("harta.out", "w", stdout);
	printf("%d\n", m);
	for (int i=1;i<=n;i++)
		for (int j=n+1;j<=2*n;j++)
			if (a[i][j]==0 && i!=j-n)
				printf("%d %d\n", i, j-n);
}	

int main ()
{
	read ();
	EK();
	write ();
	return 0;
}