Pagini recente » Cod sursa (job #545076) | Cod sursa (job #1980708) | Cod sursa (job #2294199) | Cod sursa (job #2894133) | Cod sursa (job #931307)
Cod sursa(job #931307)
#include <stdio.h>
#define FIN "harta.in"
#define FOUT "harta.out"
#define NMAX 203
#define INF 0x3f3f3f3f
int N, c[NMAX][NMAX], f[NMAX][NMAX], iter, d[NMAX], pred[NMAX];
int begin, ended, coada[NMAX];
void in (int val)
{
coada[ended] = val;
++ ended;
}
int out ()
{
int temp = coada[begin];
++ begin;
return temp;
}
void bf ()
{
int v, i;
d[1] = iter;
begin = ended = 0;
in (1);
while (begin != ended)
{
v = out ();
for (i = 1; i <= 2*N + 2; ++ i)
if (c[v][i] > f[v][i] && d[i] != iter)
{
d[i] = iter;
pred[i] = v;
if (i == 2*N + 2)
return;
in (i);
}
}
}
void ford_fulk (int s, int t)
{
int min, i;
++ iter;
while (d[t] != iter)
{
min = INF;
bf ();
if (d[t] != iter)
break;
i = t;
while (pred[i])
{
if (min > c[pred[i]][i] - f[pred[i]][i])
min = c[pred[i]][i] - f[pred[i]][i];
i = pred[i];
}
i = t;
while (pred[i])
{
f[pred[i]][i] += min;
f[i][pred[i]] -= min;
i = pred[i];
}
++ iter;
}
}
int
main ()
{
int x, y, rez = 0;
freopen (FIN, "rt", stdin);
freopen (FOUT, "wt", stdout);
scanf ("%d", &N);
for (int i = 1; i <= N; ++ i)
{
scanf ("%d%d", &x, &y);
rez += x;
c[1][i+1] = x;
c[N+i+1][2*N+2] = y;
}
for (int i = 2; i <= N + 1; ++ i)
for (int j = N + 2; j <= 2*N + 1; ++ j)
if (i + N != j)
c[i][j] = 1;
ford_fulk (1, 2*N + 2);
printf ("%d\n", rez);
for (int i = 2; i <= N + 1; ++ i)
for (int j = N + 2; j <= 2*N + 1; ++ j)
if (f[i][j])
printf ("%d %d\n", i - 1, j - N - 1);
return 0;
}