Cod sursa(job #182513)

Utilizator amadaeusLucian Boca amadaeus Data 20 aprilie 2008 23:10:37
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define NX 210

int S, T, N, flow, cap[ NX ][ NX ], pi[ NX ];
queue< int > Q;

void cit() {
	int i, j;
	
	scanf( "%d", &N );
	S = 0; T = 2*N + 1;
	for( i = 1; i <= N; i++ )
		scanf( "%d %d ", &cap[i+N][T], &cap[0][i] );
	for( i = 1; i <= N; i++ )
		for( j = 1; j <= N; j++ )
			if( i != j )
				cap[i][j+N] = 1;
	N = T;
}

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

void rez() {
	int i, bot, u, v, z;

	while( 1 ) {
		memset( pi, -1, sizeof( pi ) );
		pi[ S ] = -2;

		while( !Q.empty() ) Q.pop();
		
		Q.push( S );
		while( !Q.empty() && pi[T] == -1 ) {
			u = Q.front(), Q.pop();
			for( i = 0; i <= N; i++ )
				if( cap[u][i] && pi[i] == -1 )
					pi[i] = u, Q.push( i );
		}

		if( pi[ T ] == -1 )
			break;

		for( z = 0; z <= N; z++ ) if( cap[z][T] && pi[z] != -1 ) {
			bot = cap[z][T];
			for( u = pi[z], v = z; u >= 0; v = u, u = pi[u] )
				bot = MIN( bot, cap[u][v] );

			if( bot <= 0 ) continue;

			cap[z][T] -= bot;
			cap[T][z] += bot;
			for( u = pi[z], v = z; u >= 0; v = u, u = pi[u] )
				cap[u][v] -= bot,
				cap[v][u] += bot;

			flow += bot;
		}
	}
}

void scr() {
	int i, j;
	
	printf( "%d\n", flow );
	N >>= 1;

	for( i = 1; i <= N; i++ )
		for( j = 1; j <= N; j++ )
			if( cap[i][ j+N ] == 0 && i!=j )
				printf( "%d %d\n", i, j );
}

int main() {
	freopen( "harta.in", "r", stdin );
	freopen( "harta.out", "w", stdout );

	cit();
	rez();
	scr();

	return 0;
}