Cod sursa(job #79353)

Utilizator vladcoderVlad Ion vladcoder Data 21 august 2007 21:04:19
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>
#include <string.h>
#include <math.h>

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

int gext[NMAX], gint[NMAX], FLOW[NMAX][NMAX], CAP[NMAX][NMAX];
int SEL[NMAX], Q[NMAX], T[NMAX];
int N, i, j, sursa, dest, flow = 0;
FILE * fin, * fout;

void BFS( int start )
{
	int p, u, nod;
	memset( SEL, 0, sizeof(SEL) );
	memset( T, 0, sizeof(T) );
	p = 1; u = 1; Q[p] = start; T[start] = - 1; SEL[start] = 1;
	while ( ( p <= u ) && (!SEL[dest] ) )
	{
		nod = Q[p];
		for ( i = sursa; i <= dest; i++ )
			if (!SEL[i])
			if ( CAP[nod][i] - FLOW[nod][i] > 0 )
			{
				T[i] = nod; u++; Q[u] = i; SEL[i] = 1;
			}else
				if (FLOW[i][nod] > 0 )
				{
					T[i] = - nod; u++; Q[u] = i; SEL[i] = 1;
				}
				p++;
	}
}

void RELAX( int xp )
{
	int  tata;
	while (T[xp] != -1 )
	{
		tata = abs( T[xp] );
		if ( T[xp] > 0 ) FLOW[tata][xp]++; else FLOW[xp][tata]--;
        xp = tata;
	}
}

int main()
{
	fin = fopen( FIN, "r" );
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%d\n", &N );
	for( i = 1; i <= N; i++ ) fscanf( fin, "%d %d\n", &gext[i], &gint[i] );
	sursa = 1; dest = 2 * N + 2;
    memset( CAP, 0, sizeof(CAP) );
	memset( FLOW, 0, sizeof(FLOW) );
	for( i = 2; i <= N + 1; i++ ) CAP[sursa][i] = gext[i-1];
	for( i = N + 2; i < dest; i++) CAP[i][dest] = gint[i-N-1];
	for( i = 2; i <= N + 1; i++)
		for( j = N + 2; j < dest; j++ )	CAP[i][j] = 1;
	for( i = 2; i <= N + 1; i++ ) CAP[i][i+N] = 0;
	flow = 0;
	do	
	{
		BFS(sursa);
		if (SEL[dest]) 
		{
			flow++;
			RELAX(dest);
		}
	}while(SEL[dest]);
	fprintf( fout, "%d\n", flow );
	for( i = 2; i <= N + 1; i++)
		for( j = N + 2; j < dest; j++)
			if (FLOW[i][j]) fprintf( fout, "%d %d\n", i - 1, j - N - 1 );
	fclose(fin);
	fclose(fout);
	return 0;
}