Cod sursa(job #220165)

Utilizator MirageRobert Sandu Mirage Data 9 noiembrie 2008 18:45:52
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>
#include<string.h>
#define L 202
int n,nr,a[L][L],v[L][L],w[L];
int bfs(){
	int i,j,x,act,q[L];
	memset(w,-1,sizeof(w));
	x=0;
	q[0]=0;
	w[0]=-1;
	for(j=0;j<=x;++j){
		act=q[j];
		for(i=0;i<=2*n+1;++i){
			if(w[i]==-1&&a[act][i]>v[act][i]){
				q[++x]=i;
				w[i]=act;
				if(i==2*n+1)
					return true;
			}
		}
	}
	return false;
}
int main(){
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%d",&n);
	int i,j,x,y,q;
	for(i=1;i<=n;++i){
		scanf("%d%d",&x,&y);
		a[0][i]=x;
		a[i+n][2*n+1]=y;
		nr+=x;
		for(j=1;j<=n;++j)
			if(j!=i)
				a[i][j+n]=1;
	}
	printf("%d\n",nr);
	while(bfs()){
		q=2*n+1;
		while(q){
			v[w[q]][q]++;
			v[q][w[q]]--;
			q=w[q];
		}
	}
	for(i=1;i<=n;++i){
		for(j=n+1;j<2*n+1;++j){
			if(v[i][j]>0)
				printf("%d %d\n",i,j-n);
		}
	}
	return 0;
}