Cod sursa(job #222857)

Utilizator galacticaBattlestar galactica Data 25 noiembrie 2008 19:40:16
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
#define N 210
int nr[N],f[N][N],c[N][N],t[N],n,s;

bool bf()
{
	int x,y,p=0,u=0,coada[N];
	bool viz[N]={false};
	coada[u++]=0;
	viz[0]=true;
	while(p!=u)
	{
		x=coada[p++];
		for(y=1 ; y<=2*n+1 ; ++y)
			if(c[x][y]>f[x][y] && viz[y]==false)
			{
				coada[u++]=y;
				viz[y]=true;
				t[y]=x;
				if(y==2*n+1)
					return true;
			}
	}
	return false;
}

void actualizare()
{
	int x=2*n+1;
	while(x)
	{
		++f[t[x]][x];
		--f[x][t[x]];
		x=t[x];
	}
}
void flux(){
	while(bf())
	{
		//m=minim();
		actualizare();
	}
}

void prelucrare(){
	int i,j;
	printf("%d\n",s);
	for(i=1;i<=n;++i){
		for(j=n+1;j<=n<<1;++j)
			if(f[i][j])
				printf("%d %d\n",i,j-n);
	}
}
int main(){
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%d%d",&nr[i],&nr[i+n]);
		c[0][i]=nr[i];
		c[i+n][2*n+1]=nr[i+n];
		s+=nr[i];
	}
	for(i=1;i<=n;++i)
		for(j=n+1;j<=2*n;++j)
			if(j-i!=n)
				c[i][j]=1;
	flux();
	prelucrare();
	fclose(stdin);
	fclose(stdout);
	return 0;
}