Cod sursa(job #4041)

Utilizator vlad_DVlad Dumitriu vlad_D Data 30 decembrie 2006 03:25:34
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <stdio.h>
int R[222][222];
		int last[300];
		int cost[300];
		int used[300];
		int Usize;
int N, i, j, k;
int SI, SO, flow, SOL;
int coada[400], start, stop;
void cufunda(int node) {
     int l = 2*node;
     int r = l+1;
     int mx = node;
     if (l<= Usize && cost[used[l]] > cost[used[node]]) mx = l;
     if (r<=Usize && cost[used[r]] > cost[used[mx]]) mx = r;
     if (mx == node) return;
     int aux = used[node]; used[node]=used[mx]; used[mx] = aux;
     cufunda(mx);

     }
void urca(int node) {
     int l = node/2;
     int mx = node;
     if (l>0 && cost[used[l]] < cost[used[node]]) mx = l;
     if (mx == node) return;
     int aux = used[node]; used[node]=used[mx]; used[mx] = aux;
     urca(mx);
    }
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) {
		for (i=0; i<=SO; i++) {last[i] = cost[i] = 0; used[i]=i;}
                Usize = SO;
		cost[SI] = 9999;
                used[1] = SI; used[SI] = 1;
		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[1];
			used[1] = used[Usize];
      			Usize--;
                        cufunda(1);
                        /*ia maximu*/
			for (i=1; i<=Usize; i++) {
				mx = R[node][used[i]];
				if (cost[node] < mx) mx = cost[node];
				if (cost[used[i]] < mx) {cost[used[i]] = mx; last[used[i]] = node; urca(i); }
				}
			}
		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;
}