Cod sursa(job #189973)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 19 mai 2008 15:54:43
Problema Taramul Nicaieri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FIN "harta.in"
#define FOUT "harta.out"

#define ABS( a ) (a) < 0 ? -(a) : (a)


#define NMAX 102

int C[NMAX][NMAX], F[NMAX][NMAX];
int SEL[NMAX], Q[NMAX], T[NMAX];
int N, S, D, flow = 0;

void BFS()
{
	int p = 1, u = 1, nod, i;
	memset( SEL, 0, sizeof(SEL));
	Q[p] = S; T[S] = 0; SEL[S] = 1;
	while( p <= u )
	{
		nod = Q[p];
		for( i = S; i <= D; i++ )
			if( !SEL[i] )
				if( C[nod][i] - F[nod][i] > 0 )
					Q[++u] = i, T[i] = nod, SEL[i] = 1;
				else
					if( F[i][nod] > 0 )
						Q[++u] = i, T[i] = -nod, SEL[i] = 1;
		p++;
	}
}

void Relax( int x )
{
	int d;
	while( T[x] != 0 )
	{
		d = ABS(T[x]);
		if( T[x] > 0 )
			F[d][x]++;
		else
			F[x][d]--;
		x = d;
	}
}

void FLOW()
{
	do
	{
		BFS();
		if( SEL[D])
			Relax(D), flow++;
	}while(SEL[D]);
}

int main()
{
	int i, j;
	FILE * fin = fopen( FIN, "r" );
	FILE * fout = fopen( FOUT, "w" );
	fscanf( fin, "%d", &N );
	S = 1; D = 2 * N + 2;
	for( i = 1; i <= N; i++ )
	  fscanf( fin, "%d%d", &C[S][i+1], &C[i+N+1][D]);
	for( i = 2; i <= N + 1; i++ )
		for( j = N + 2; j <= 2 * N + 1; j++ )
			if( j - i != N )
				C[i][j] = 1;
	
	
	FLOW();
	fprintf( fout, "%d\n", flow );
	for( i = 2; i <= N + 1; i++ )
		for( j = N + 2; j < D; j++ )
			if( F[i][j] )
				fprintf( fout, "%d %d\n", i - 1, j - N - 1);
	fclose( fin );
	fclose( fout );
	
	
	return 0;
	
}