Cod sursa(job #287018)

Utilizator katakunaCazacu Alexandru katakuna Data 24 martie 2009 14:20:19
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
using namespace std;
#include <cstdio>
#include <algorithm>

#define Nmax 256
#define INF 1 << 30

int N, n, M, C[Nmax][Nmax], F[Nmax][Nmax], t, c[Nmax], j, i, Min;
int T[Nmax];

void citire(){

	int x, y, i;
	FILE *f = fopen("harta.in", "r");
	
	fscanf(f,"%d",&n);
	N = 2*n + 1;
	for(i=1; i<=n; i++){
		fscanf(f,"%d %d",&x, &y);
		M+=x;
		C[0][i] = x; C[i+n][ N] = y;
		
		for(j=n+1; j < N; j++)
			if( i != j - n )
				C[i][j] = 1;
	}
	
	fclose(f);
}

int BF(){

	int p, u = 1, i, ok = 0;
	memset(T, 0xff, (N+2) * sizeof(int));
	
	c[1] = 0;
	T[0] = 0;
	
	for(p = 1; p <= u; p++)
		for(i = 0; i <= N; i++){
			if( C[c[p]][i] > F[c[p]][i] && T[i] == -1){
				if( i == N ){ok =1 ; continue;}
				c[++u] = i;
				T[i] = c[p];
			}
		}
	
	return ok;
}

void flux(){
	
	while( BF() ){		
		for(i = n+1; i < N; i++){
			if( T[i] ){
				T[N] = i;
				for(t = N, Min = INF; t != 0; t = T[t])
					Min = min (Min, C[T[t]][t] - F[T[t]][t] );
				
				for(t = N; t != 0; t = T[t])
					F[T[t]][t]+=Min ,F[t][T[t]]-=Min  ;
				
			}
		}
	}
}


void afisare(){

	int i, j;
	FILE *g = fopen("harta.out", "w");
	fprintf(g,"%d\n",M);
	for(i=1; i<=n; i++)
		for(j = n+1; j < N ; j++)
			if( i != (j - n) && F[i][j] > 0 )
				fprintf(g,"%d %d\n",i, j-n);
	
	fclose(g);
}

int main(){

	citire();
	flux();
	afisare();

	return 0;
}