Pagini recente » Cod sursa (job #2917150) | Cod sursa (job #1042151) | Cod sursa (job #657065) | Cod sursa (job #2421014) | Cod sursa (job #670169)
Cod sursa(job #670169)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
#define maxN 210
#define PB push_back
#define inf (1 << 30)
bool cont[maxN];
int cp[maxN][maxN], fl[maxN][maxN], tata[maxN];
int sol, N;
queue <int> Q;
vector <int> lista[maxN];
int poti_pompa ()
{
Q.push (0);
memset (cont, 0, sizeof (cont));
while (! Q.empty ())
{
int nod = Q.front();
Q.pop();
for (unsigned int i = 0; i < lista[nod].size(); ++ i)
{
int nod2 = lista[nod][i];
if (cp[nod][nod2] - fl[nod][nod2] == 0) continue;
if (cont[nod2]) continue;
Q.push (nod2);
tata[nod2] = nod;
cont[nod2] = true;
}
}
if ( ! cont[N * 2 + 1] ) return 0;
int nod = 2 * N + 1;
int minim = inf;
while (nod)
{
minim = min (minim, cp[tata[nod]][nod] - fl[tata[nod]][nod]);
nod = tata[nod];
}
nod = 2 * N + 1;
while (nod)
{
fl[tata[nod]][nod] += minim;
fl[nod][tata[nod]] -= minim;
nod = tata[nod];
}
sol += minim;
return 1;
}
int main()
{
freopen ("harti.in", "r", stdin);
freopen ("harti.out", "w", stdout);
scanf ("%d", &N);
for (int i = 1; i <= N; ++ i)
{
int in, out;
scanf ("%d %d", &in, &out);
cp[0][i] = in;
cp[i + N][2 * N + 1] = out;
lista[0].PB (i);
lista[i].PB (0);
lista[i + N].PB (2 * N + 1);
lista[2 * N + 1].PB (i + N);
}
for (int i = 1; i <= N; ++ i)
for (int j = N + 1; j <= 2 * N; ++ j)
{
if (j - N == i) continue;
cp[i][j] = 1;
lista[i].PB (j);
lista[j].PB (i);
}
while (poti_pompa());
printf ("%d \n", sol);
for (int i = 1; i <= N; ++ i)
for (int j = N + 1; j <= 2 * N; ++ j) if (fl[i][j] == 1) printf ("%d %d\n", i, j - N);
return 0;
}