Cod sursa(job #4040)

Utilizator vlad_DVlad Dumitriu vlad_D Data 30 decembrie 2006 02:42:44
Problema Taramul Nicaieri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
int R[222][222];
int N, i, j, k;
int SI, SO, flow, SOL;
int coada[400], start, stop;
int main() {

	freopen("harta.in", "r", stdin);
	freopen("harta.out", "w", stdout);
	scanf("%d", &N);
	for (i=1; i<=N; i++)
		for (j=N+1; j<=2*N; j++) if (i != j - N) R[i][j] = 1;
	SI= 2*N+1, SO= 2*N+2;
	for (i=1; i<=N; i++) {
		int A, B;
		scanf("%d %d", &A, &B);
		R[SI][i] = A;
                SOL+=A;
		R[N+i][SO]= B;
		}
	flow = 0;
	while (1) {
		int last[300];
		int cost[300];
		int used[300];
		for (i=0; i<=SO; i++) {last[i] = cost[i] = 0; used[i]=i;}
		int Usize = SO;
		cost[SI] = 9999;
		while (1) {
			if (Usize ==0) break;
			int mx = 1;
			for (i=2; i<=Usize; i++) if (cost[used[i]] > cost[used[mx]]) mx = i;
			int node = used[mx];
			used[mx] = used[Usize];
			Usize--;
			for (i=1; i<=SO; i++) {
				mx = R[node][i];
				if (cost[node] < mx) mx = cost[node];
				if (cost[i] < mx) {cost[i] = mx; last[i] = node;}
				}
			}
		if (cost[SO] == 0) break;
		flow+=cost[SO];
		int cp = SO, cp2 = last[SO];
		while (cp2!=0) {
			R[cp2][cp] -= cost[SO];
			R[cp][cp2] += cost[SO];
			cp = cp2;
			cp2= last[cp2];
			}
		//cauta drum de la SI la SO prin R
		//if min_cap e 0 break
		//flow+=min_cap
		//actualizeaza Rezidualu

		}
	//if (flow == cu toate) solutie
printf("%d\n", SOL);
for (i=1; i<=N; i++)
for (j=1; j<=N; j++)
if (R[N+j][i] == 1) {
	printf("%d %d\n", i, j);
	}
	return 0;
}