Cod sursa(job #444867)

Utilizator klamathixMihai Calancea klamathix Data 21 aprilie 2010 22:13:33
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 401;
const int maxm = maxn * maxn;
const int SURSA = 300;
const int DEST = 299;

queue <int> Q;
vector <int> G[maxn];
int  i , j , n , a , b , res;
int C[maxn][maxn] , F[maxn][maxn] , dad[maxn];
bool seen[maxn];

bool BF ()
{
	int i;
	memset ( seen , 0 , sizeof(seen));
	seen[SURSA] = 1;
	while ( ! Q.empty() ) Q.pop();
	
	Q.push(SURSA);
	
	for( ; !Q.empty() ; ) {
		int node = Q.front() ; Q.pop();
		if ( node == DEST ) break;
		for(i = 0 ; i < G[node].size() ; ++i )
		{
			int act = G[node][i];
			if ( F[node][act] < C[node][act] && seen[act] == 0 ) {
				Q.push(act);
				dad[act] = node;
				seen[act] = 1;
			}
		}
	}
return seen[DEST];
}

void flow ()
{
	int i;
	
	for( ; BF() ; ) {
		for ( i = 0 ; i < G[DEST].size() ;++i ) {
			int act = G[DEST][i];
			if ( seen[act] == 0 || F[act][DEST] == C[act][DEST] ) continue ;
			
			int minflow = 1000001;
			dad[DEST] = act;
			
			for( act = DEST; act != SURSA ; act = dad[act] ) 
				minflow = min ( minflow ,C[dad[act]][act] - F[dad[act]][act]);
			for( act = DEST ; act != SURSA ; act = dad[act] )
				F[dad[act]][act] += minflow ,
				F[act][dad[act]] -= minflow;
		}
	}
}
		

int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	
	for( scanf("%d",&n) , i = 1  ; i <= n ; ++i ) {
		scanf("%d %d",&a,&b);
		C[SURSA][i] = a;
		C[i + 100][DEST] = b;
		res += a;
	}
	
	for( i = 1 ; i <= n ; ++i ) {
		G[SURSA].push_back(i);
		G[i].push_back(SURSA);
		G[i + 100].push_back(DEST);
		G[DEST].push_back(i + 100);
	}
	
	for( i = 1 ; i <= n ; ++i )
		for( j = 1 ; j <= n ; ++j ) {
			if ( i != j ) C[i][j + 100] = 1;
			G[i].push_back(j + 100);
			G[j + 100].push_back(i);
		}
		
	flow ();
	printf("%d\n",res);
			
	for( i = 1 ; i <= n ; ++i )
		for( j = 1 ; j <= n ; ++j )
			if ( F[i][j + 100] == 1 ) printf("%d %d\n",i,j);
	
return 0;
}