Cod sursa(job #282522)

Utilizator alisssiaMititelu Andra alisssia Data 17 martie 2009 20:20:24
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
using namespace std;
#include<cstdio>
#define Nmax 101
int n,s,d,viz[202],t[202],f[202][202],c[202][202];
int minim(int i,int j) {if(i<j) return i;return j;}

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

void flux()
{
	int i,j,min;
	
	while(bfs())
		for(i=1;i<=n;i++)
		{
			min=c[n+i][d]-f[n+i][d];
			for(j=n+i;j;j=t[j])
				min=minim(min,c[t[j]][j]-f[t[j]][j]);
			if(min>0)
			{
			for(j=n+i;j;j=t[j])
			{
				f[t[j]][j]+=min;
				f[j][t[j]]-=min;
			}
			f[n+i][d]+=min;
			f[d][n+i]-=min;
			}
		}
}

void read()
{
	int i,j;
	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][d]);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j) c[i][n+j]=1;
}

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