Pagini recente » Cod sursa (job #3125069) | Cod sursa (job #1305935) | Borderou de evaluare (job #1036962) | Cod sursa (job #1525476) | Cod sursa (job #479327)
Cod sursa(job #479327)
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int n, up[205];
int c[205][205], f[205][205];
vector <int> v[205];
inline int calc (int a, int b) {return c[a][b] - f[a][b];}
inline int minim (int a, int b) {return a < b ? a : b;}
int bfs ()
{
memset (up, -1, sizeof (up));
up[0] = -2;
int nod;
queue <int> q;
q.push (0);
while (!q.empty ())
{
nod = q.front ();
q.pop ();
for (vector <int> :: iterator it = v[nod].begin (); it != v[nod].end (); it ++)
if (up[*it] == -1 && c[nod][*it] > f[nod][*it])
{
up[*it] = nod;
if (*it == 2 * n + 1)
return 1;
q.push (*it);
}
}
return 0;
}
void flux ()
{
int nod, min;
while (bfs ())
{
nod = 2 * n + 1;
min = calc (up[nod], nod);
while (up[nod] != -2)
{
min = minim (min, calc (up[nod], nod));
nod = up[nod];
}
nod = 2 * n + 1;
while (up[nod] != -2)
{
f[up[nod]][nod] += min;
f[nod][up[nod]] -= min;
nod = up[nod];
}
}
}
int main ()
{
freopen ("harta.in", "r", stdin);
freopen ("harta.out", "w", stdout);
scanf ("%d", &n);
int i, j, s = 0, cap;
for (i = 1; i <= n; i ++)
{
scanf ("%d", &cap);
s += cap;
c[0][i] = cap;
v[0].push_back (i);
v[i].push_back (0);
scanf ("%d", &cap);
c[n + i][2 * n + 1] = cap;
v[n + i].push_back (2 * n + 1);
v[2 * n + 1].push_back (n + i);
}
for (i = 1; i <= n; i ++)
for (j = n + 1; j <= n + n; j ++)
if (j - i != n)
{
c[i][j] = 1;
v[i].push_back (j);
v[j].push_back (i);
}
flux ();
printf ("%d\n", s);
for (i = 1; i <= n; i ++)
for (j = 1; j <= n; j ++)
if (f[i][j + n] > 0)
printf ("%d %d\n", i, j);
return 0;
}