Cod sursa(job #487935)

Utilizator Addy.Adrian Draghici Addy. Data 26 septembrie 2010 22:51:38
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 205

int C[NMAX][NMAX], F[NMAX][NMAX], Q[NMAX], T[NMAX], viz[NMAX], S, D, n, flux_max;

void citire (), flux (), afisare ();

int main () {
	
	citire ();
	
	flux ();
	
	afisare ();
	
	return 0;
}

void citire () {
	
	freopen ("harta.in", "r", stdin);
	
	int i, j, x, y;
	
	scanf ("%d", &n);
	
	S = 0, D = 2 * n + 1;
	for (i = 1; i <= n; i++) {
		scanf ("%d %d", &x, &y);
		C[S][i] = x, C[i + n][D] = y;
		
		for (j = n + 1; j <= 2 * n; j++)
			if (i != j - n)
				C[i][j] = 1;
	}
}

int BFS () {
	
	int i, p, u, nod, ok;
	
	memset (viz, 0, sizeof (viz));
	
	Q[1] = S, T[S] = -1, viz[S] = 1; ok = 0;
	for (p = u = 1; p <= u; p++) {
		nod = Q[p];
		for (i = 1; i <= D; i++)
			if (!viz[i] && C[nod][i] > F[nod][i]) {
				if (i == D) {
					ok = 1; continue;
				}
				
				Q[++u] = i;
				viz[i] = 1, T[i] = nod;
			}
	}
	
	return ok;
}

void flux () {
	
	int i, fr, nod, minim;
	
	while (BFS ()) {
		for (i = n + 1; i <= 2 * n; i++) {
			fr = i;
			
			minim = C[fr][D] - F[fr][D];
			
			for (nod = fr; T[nod] != -1; nod = T[nod])
				minim = min (minim, (C[T[nod]][nod] - F[T[nod]][nod]));
			
			for (T[D] = fr, nod = D; T[nod] != -1; nod = T[nod]) {
				F[T[nod]][nod] += minim;
				F[nod][T[nod]] -= minim;
			}
			
			flux_max += minim;
		}
	}
}

void afisare () {
	
	freopen ("harta.out", "w", stdout);
	
	int i, j;
	
	printf ("%d\n", flux_max);
	
	for (i = 1; i <= n; i++)
		for (j = n + 1; j <= 2 * n; j++)
			if (F[i][j] == 1 && i != j - n)
				printf ("%d %d\n", i, j - n);
}