Cod sursa(job #571912)

Utilizator avram_florinavram florin constantin avram_florin Data 4 aprilie 2011 21:12:22
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<cstdio>
#include<vector>
#include<queue>

#define minim(a, b) ((a)<=(b)?(a):(b))
#define InFile "harta.in"
#define OutFile "harta.out"

using namespace std;

const int MaxN = 1 << 8;
const int INF = 0x3f3f3f3f;

int n,S,D,C[MaxN][MaxN],F[MaxN][MaxN],T[MaxN],viz[MaxN];
vector<int> G[MaxN];
queue<int> Q;

void read_BuildGraph()
{
	freopen( InFile , "r" , stdin );
	scanf("%d" , &n );
	S = 2*n+1;
	D = 2*n+2;
	int i,j,x,y;
	for( i = 1 ; i <= n ; i++ )
		{
			scanf("%d%d" , &x , &y );
			G[S].push_back(i);
			G[i].push_back(S);
			C[S][i] = x;
			G[n+i].push_back(D);
			G[D].push_back(n+i);
			C[n+i][D] = y;
		}
	for( i = 1 ; i <= n ; i++ )
		for( j = 1 ; j <= n ; j++ )
			if( i != j )
				{
					G[i].push_back(n+j);
					G[n+j].push_back(i);
					C[i][n+j] = 1;
				}
}

int BFS(int s , int d )
{
	memset(viz,0,sizeof(viz));
	viz[s] = 1;
	Q.push(s);
	while( !Q.empty() )
		{
			int nod;
			vector<int>::iterator it;
			nod = Q.front();
			Q.pop();
			if( nod == d )
				continue;
			for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
				if( !viz[*it] && C[nod][*it] > F[nod][*it] )
					{
						viz[*it] = 1;
						T[*it] = nod;
						Q.push(*it);
					}
		}
	return viz[d];
}

int flux()
{
	int Flux = 0;
	while( BFS(S,D) )
		{
			int minflux,nod;
			vector<int>::iterator it;
			for( it = G[D].begin() ; it != G[D].end() ; ++it )
				if( T[*it] && C[*it][D] > F[*it][D] )
					{
						T[D] = *it;
						minflux = INF;
						nod = D;
						while( nod != S )
							{
								minflux = minim(minflux,C[T[nod]][nod] - F[T[nod]][nod] );
								nod = T[nod];
							}
						nod = D;
						while( nod != S )
							{
								F[T[nod]][nod] += minflux;
								F[nod][T[nod]] -= minflux;
								nod = T[nod];
							}
						Flux += minflux;
					}
		}
	return Flux;
}

void write()
{
	freopen( OutFile , "w" , stdout );
	printf("%d\n" , flux());
	int i,j;
	for( i = 1 ; i <= n ; i++ )
		for( j = 1 ; j <= n ; j++ )
			if( i != j && C[i][n+j] == F[i][n+j] )
				printf("%d %d\n" , i , j);
}

int main()
{
	read_BuildGraph();
	write();
	return 0;
}