Cod sursa(job #480579)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 28 august 2010 18:14:37
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define Nmax 105*2
#define INF 2147000000
#define pb push_back

using namespace std;

queue< int > Q;
vector< int > v[Nmax];
int F[Nmax][Nmax],C[Nmax][Nmax];
int prev[Nmax], use[Nmax];
int n,S,D;

inline int Minim(int x,int y){ return x<y ? x:y; }

int bf(){
	int x;
	vector< int >::iterator it;
	memset(use,0,sizeof(use));
	Q.push(S); use[S]=1;
	
	while( ! Q.empty() ){
		x=Q.front(); Q.pop();
		
		for(it=v[x].begin(); it!=v[x].end(); ++it)
			if( F[x][*it] < C[x][*it] && !use[*it] ){
				use[*it]=1;
				prev[*it]=x;
				Q.push(*it);
			}
	}
	return use[D];
}
	

void flux(){
	vector< int >::iterator it;
	int fmin,wh;
	
	while( bf() )
		for(it=v[D].begin(); it!=v[D].end(); ++it)
			if( use[*it] ){
				prev[D]=*it; fmin=INF;
				for( wh=D; wh!=S && fmin; wh=prev[wh] )
					fmin=Minim(fmin,C[prev[wh]][wh]-F[prev[wh]][wh]);
				
				if( fmin == 0 ) continue;
				
				for( wh=D; wh!=S; wh=prev[wh] ){
					F[prev[wh]][wh] += fmin;
					F[wh][prev[wh]] -= fmin;
				}
			}
}

int main(){
	int i,j,x,y,m=0;
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%d",&n);
	D=2*n+1; S=2*n+2;
	for(i=1;i<=n;++i){
		scanf("%d%d",&x,&y);
		m += x;
		v[S].pb(i); v[i].pb(S); C[S][i]=x;
		v[i+n].pb(D); v[D].pb(i+n); C[i+n][D]=y;
		for(j=1;j<=n;++j)
			if(i!=j){
				v[i].pb(j+n); v[j+n].pb(i);
				C[i][j+n]=1;
			}
	}
	
	flux();
	
	printf("%d\n",m);
	for(i=1;i<=n;++i)
		for(j=n+1;j<=2*n;++j)
			if( F[i][j] ) printf("%d %d\n",i,j-n);
	fclose(stdin); fclose(stdout);
	return 0;
}