Cod sursa(job #719259)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 21 martie 2012 17:46:40
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 210
#define INF 0x3f3f3f3f
#define pb push_back

int N, gin, gout, i, j, Nod, FluxCt, Flux, S, D;
int C[NMAX][NMAX], F[NMAX][NMAX], T[NMAX];
vector< int > G[NMAX];
bool Used[NMAX];

inline bool BF()
{
	memset( T, 0, sizeof(T) );
	queue< int > Q;
	Q.push( S );
	memset( Used, 0, sizeof(Used) );
	Used[S] = true;
	
	while( !Q.empty() )
	{
		Nod = Q.front();
		Q.pop();
		
		for( vector< int >::iterator it = G[Nod].begin(); it != G[Nod].end(); ++it )
			if( !Used[*it] && C[Nod][*it] > F[Nod][*it] )
			{
				Used[*it] = true;
				T[*it] = Nod;
				Q.push( *it );
			}
	}
	
	return Used[D];
}

int main()
{
	freopen("harta.in", "r", stdin);
	freopen("harta.out", "w", stdout);
	
	memset( C, 0, sizeof(C) );
	memset( F, 0, sizeof(F) );
	
	scanf("%d", &N );
	S = 0, D = 2*N + 1;
	for( i = 1; i <= N; ++i )
	{
		scanf("%d%d", &gin, &gout );
		G[S].pb( i );
		G[i].pb( S );
		G[D].pb( i + N );
		G[i + N].pb( D );
		C[S][i] = gin;
		C[i + N][D] = gout;
	}
	for( i = 1; i <= N; ++i )
		for( j = 1; j <= N; ++j )
			if( i != j )
			{
				G[i].pb( j + N );
				G[j + N].pb( i );
				C[i][j + N] = 1;
			}
	
	for( Flux = 0; BF(); )
		for( vector< int >::iterator it = G[D].begin(); it != G[D].end(); ++it )
			if( Used[*it] && F[*it][D] < C[*it][D] )
			{
				T[D] = *it;
				FluxCt = INF;
				for( Nod = D; Nod != S; Nod = T[Nod] )
					FluxCt = min( FluxCt, C[ T[Nod] ][Nod] - F[ T[Nod] ][Nod] );
				if( !FluxCt ) continue;
				for( Nod = D; Nod != S; Nod = T[Nod] )
					F[ T[Nod] ][Nod] += FluxCt, F[Nod][ T[Nod] ] -= FluxCt;
				
				Flux += FluxCt;
			}
	
	printf("%d\n", Flux );
	for( i = 1; i <= N; ++i )
		for( j = 1; j <= N; ++j )
			if( F[i][j + N] )
				printf("%d %d\n", i, j );
	
	return 0;
}