Cod sursa(job #282086)

Utilizator alisssiaMititelu Andra alisssia Data 16 martie 2009 20:46:30
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
using namespace std;
#include<cstdio>
#include<iostream>
#define Nmax 101
int f[Nmax*2+2][Nmax*2+2],c[Nmax*2+2][Nmax*2+2],viz[Nmax*2+2],q[Nmax*2+2],s=0,d,m,n,t[Nmax*2+2];

int bfs()
{
	q[0]=s;
	viz[s]=1;
	t[s]=0;
	int p=0,x,i,u=0;
	while(p<=u && !viz[d])
	{
		x=q[p];
		p++;
		for(i=0;i<=2*n+1;i++)
			if(!viz[i] && f[x][i]<c[x][i])
			{
				viz[i]=1;
				t[i]=x;
				q[++u]=i;
			}
	}
if(viz[d]) return 0;
return 1;
}

void flux()
{
	int i,l[Nmax*2+2],min,lg;
	do
	{
		for(i=0;i<=2*n+2;i++) {viz[i]=0;t[i]=-1;}
		if(bfs()) return; 
		l[0]=d; lg=0; min=c[ t[ l[0] ] ][d]-f[ t[ l[0] ] ][d];
		while(l[lg]!=s)
		{
			++lg;
			l[lg]=t[l[lg-1]];
			if(c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]]<min)
				min=c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]];
		}
		for(i=lg;i>0;i--)
			{f[l[i]][l[i-1]]+=min;f[l[i-1]][l[i]]-=min;}
	}while(1);
}

void read()
{
	int i;
	freopen("harta.in","r",stdin);
	scanf("%d",&n); d=2*n+1;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&c[0][i],&c[n+i][2*n+1]);
	}
}

int main()
{
	int i,j;
	read();
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j) c[i][n+j]=1;
	flux();
	for(i=1;i<=n;i++) m+=c[0][i];
	
	/*for(i=1;i<=n;i++)
		{for(j=1;j<=n;j++)
			cout<<f[i][n+j]<<" ";
		cout<<endl;}*/
	freopen("harta.out","w",stdout);
	printf("%d\n",m);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		if(f[i][n+j]) printf("%d %d\n",i,j);
	return 0;
}