Pagini recente » Cod sursa (job #2952074) | Cod sursa (job #1519228) | Cod sursa (job #2958239) | Cod sursa (job #2174760) | Cod sursa (job #487935)
Cod sursa(job #487935)
#include <cstdio>
#include <algorithm>
using namespace std;
#define NMAX 205
int C[NMAX][NMAX], F[NMAX][NMAX], Q[NMAX], T[NMAX], viz[NMAX], S, D, n, flux_max;
void citire (), flux (), afisare ();
int main () {
citire ();
flux ();
afisare ();
return 0;
}
void citire () {
freopen ("harta.in", "r", stdin);
int i, j, x, y;
scanf ("%d", &n);
S = 0, D = 2 * n + 1;
for (i = 1; i <= n; i++) {
scanf ("%d %d", &x, &y);
C[S][i] = x, C[i + n][D] = y;
for (j = n + 1; j <= 2 * n; j++)
if (i != j - n)
C[i][j] = 1;
}
}
int BFS () {
int i, p, u, nod, ok;
memset (viz, 0, sizeof (viz));
Q[1] = S, T[S] = -1, viz[S] = 1; ok = 0;
for (p = u = 1; p <= u; p++) {
nod = Q[p];
for (i = 1; i <= D; i++)
if (!viz[i] && C[nod][i] > F[nod][i]) {
if (i == D) {
ok = 1; continue;
}
Q[++u] = i;
viz[i] = 1, T[i] = nod;
}
}
return ok;
}
void flux () {
int i, fr, nod, minim;
while (BFS ()) {
for (i = n + 1; i <= 2 * n; i++) {
fr = i;
minim = C[fr][D] - F[fr][D];
for (nod = fr; T[nod] != -1; nod = T[nod])
minim = min (minim, (C[T[nod]][nod] - F[T[nod]][nod]));
for (T[D] = fr, nod = D; T[nod] != -1; nod = T[nod]) {
F[T[nod]][nod] += minim;
F[nod][T[nod]] -= minim;
}
flux_max += minim;
}
}
}
void afisare () {
freopen ("harta.out", "w", stdout);
int i, j;
printf ("%d\n", flux_max);
for (i = 1; i <= n; i++)
for (j = n + 1; j <= 2 * n; j++)
if (F[i][j] == 1 && i != j - n)
printf ("%d %d\n", i, j - n);
}