Pagini recente » Cod sursa (job #1806390) | Cod sursa (job #2148524) | Cod sursa (job #1668861) | Cod sursa (job #1292808) | Cod sursa (job #4041)
Cod sursa(job #4041)
#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;
}