Cod sursa(job #286769)

Utilizator katakunaCazacu Alexandru katakuna Data 24 martie 2009 09:54:21
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
using namespace std;
#include <cstdio>
#include <algorithm>

#define Nmax 204
#define INF 1 << 30

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

void citire(){

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

int BF(){

	int p, u = 1, i;
	memset(T, 0xff, N * sizeof(char));
	
	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){
				c[++u] = i;
				T[i] = c[p];
				if( i == N ) return 1;
			}
		}
	
	return 0;
}

void flux(){

	N = 2*n + 1;
	while( BF() )		
		for(t = N; t != 0; t = T[t]){
			F[T[t]][t]++; 
			F[t][T[t]]--; 
		}

}


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;
}