Pagini recente » Cod sursa (job #2922383) | Cod sursa (job #2317339) | Borderou de evaluare (job #1569667) | Cod sursa (job #1131107) | Cod sursa (job #4040)
Cod sursa(job #4040)
#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;
}