Cod sursa(job #580881)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 13 aprilie 2011 16:43:45
Problema Taramul Nicaieri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<cstdio>
#include<queue>
#define Nmax 128
#define Cmax 256
#define inf 0x3f3f3f3f
#define dr(x) (char)(N+x)
#define st(x) (x-N)


using namespace std;

int N;

char cp[Cmax][Cmax],fm[Cmax][Cmax],D,t[Cmax];

bool viz[Cmax];

int bf(){
	
	queue <char> c;
	memset(viz,0,sizeof(viz));
	
	c.push(0);
	viz[0]=1;
	
	while(!c.empty()){
		
		int nod=c.front();
		c.pop();
		for(int i=0;i<=D;++i){
			
			if(!viz[i] && cp[nod][i] > fm[nod][i]){
			
			if(i==D)
				return 1;
			
			t[i]=nod;
			viz[i]=1;
			c.push(i);
			}
		}
	}
	return 0;
}
int main(){
	
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	
	scanf("%d",&N);
	D=2*N+1;
	
	for(int i=1;i<=N;++i){
		
		int x,y;
		scanf("%d%d",&x,&y);
		
		cp[0][i]=x; //din nodul i pleaca x muchii
		cp[dr(i)][(int)D]=y; //in nodul i intra x muchii
		
		for(int j=1;j<=N;++j)
			if(i!=j)
				cp[i][dr(j)]=1; //adaugam muchii de cap 1 intre nodurile distincte
	}
	
	//calculam flux
	int flux=0;
	while(bf()){
		
		for(int i=N+1;i<D;++i)
			if(cp[i][D]>fm[i][D]){
			   t[D]=i;
			   int fmn=inf;
			   
			   for(int nod=D;nod!=0;nod=t[nod])
				   fmn=min(fmn,cp[t[nod]][nod]-fm[t[nod]][nod]);
			   
			   for(int nod=D;nod!=0;nod=t[nod]){
				   
				   fm[t[nod]][nod]+=fmn;
				   fm[nod][t[nod]]-=fmn;
			   }
			   
			   flux+=fmn;				
			}
	}
	
	printf("%d\n",flux);
	
	for(int i=1;i<=N;++i)
		for(int j=N+1;j<=2*N;++j)
			if(fm[i][j])
				printf("%d %d\n",i,st(j));
return 0;	
}