Cod sursa(job #387377)

Utilizator titusuTitus C titusu Data 27 ianuarie 2010 15:29:28
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
using namespace std;
#include <cstdio>

int a[205][205],t[205],n,fm;

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

void citire(){
	freopen("harta.in","r",stdin);
	scanf("%d",&n);
	for(int i=1 ; i<=n ; ++i)
		for(int j=1 ; j<=n ; ++j)
			if(i!=j)
				a[i][n+j]=1;
	int ies , intra;
	for(int i=1 ; i<=n ; ++i){
		scanf("%d%d",&ies, &intra);
		a[0][i]=ies;
		a[n+i][2*n+1]=intra;
	}
}

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

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

int main(){
	citire();
	ek();
	write();
	return 0;
}