Pagini recente » Cod sursa (job #1729630) | Cod sursa (job #563386) | Cod sursa (job #1275167) | Rating Mihai Zamfirescu (zamfi) | Cod sursa (job #319793)
Cod sursa(job #319793)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX_N 512
#define inf 2147000000
int n, i, j, fin, improve, flow, sol;
int C[MAX_N][MAX_N];
int Q[MAX_N], tata[MAX_N], flux[MAX_N];
void cit() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= n; i++) {
int p = 0, q = 0;
scanf("%d %d", &p, &q);
sol += p + q;
C[2 * i][2 * i + 1] = p;
C[2 * i + 2 * n][2 * i + 2 * n + 1] = q;
}
fin = 4 * n + 2;
for (i = 1; i <= n; i++) {
C[1][2 * i] = C[2 * i][2 * i + 1];
C[2 * i + 2 * n + 1][fin] = C[2 * i + 2 * n][2 * i + 2 * n + 1];
}
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i != j)
C[2 * i + 1][2 * n + 2 * j] = 1;
}
void bfs() {
int st = 0, dr = 1;
flux[1] = inf;
while (st < dr) {
st++;
for (i = 1; i <= fin; i++)
if (flux[i] == 0 && C[Q[st]][i]) {
int x = min(flux[Q[st]], C[Q[st]][i]);
flux[i] = x;
Q[++dr] = i;
tata[i] = Q[st];
}
}
improve = flux[fin];
if (!improve) return;
else {
i = fin;
while (i != 1) {
C[tata[i]][i] -= flux[fin];
C[i][tata[i]] += flux[fin];
i = tata[i];
}
}
}
void write() {
printf("%d\n", sol / 2);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (!C[2 * i + 1][2 * n + 2 * j] && C[2 * n + 2 * j][2 * i + 1])
printf("%d %d\n", i, j);
}
int main() {
cit();
/* improve = 1;
while (improve) {
Q[1] = 1;
bfs();
flow += improve;
memset(tata, 0, sizeof(tata));
memset(flux, 0, sizeof(flux));
} */
write();
return 0;
}