Pagini recente » Cod sursa (job #729916) | Cod sursa (job #2285724) | Cod sursa (job #143249) | Cod sursa (job #2590975) | Cod sursa (job #567114)
Cod sursa(job #567114)
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <bitset>
#define maxn 210
#define inf 0x3f3f3f3f
#define VIT vector <int> :: iterator
using namespace std;
int dad[maxn], f[maxn][maxn], matCap[maxn][maxn];
vector <int> G[maxn];
vector <pair <int, int> > sol;
int S, D, N;
inline bool BF ()
{
for (int i = S; i <= D; i++)
dad[i] = 0;
bitset <maxn> viz;
viz.reset ();
queue <int> Q;
Q.push (S);
int nod;
viz[S] = 1;
while (!Q.empty ()) {
nod = Q.front ();
Q.pop ();
if (nod == D) return 1;
for (VIT it = G[nod].begin (); it != G[nod].end (); it++)
if (viz[*it] == 0 && matCap[nod][*it] > f[nod][*it]) {
dad[*it] = nod;
Q.push (*it);
viz[*it] = 1;
}
}
return 0;
}
int main ()
{
freopen ("harta.in", "r", stdin);
freopen ("harta.out", "w", stdout);
scanf ("%d\n", &N);
int nod, x, y;
S = 0; D = (N << 1) + 2;
for (int i = 1; i <= N; i++) {
scanf ("%d %d\n", &x, &y);
G[S].push_back (i);
G[i + N].push_back (D);
G[D].push_back (i + N);
matCap[S][i] = matCap[i][S] = x;
matCap[i + N][D] = matCap[D][i + N] = y;
}
for (int i = 1; i <= N; i++)
for (int j = N + 1; j <= (N << 1) + 1; j++)
if (i != j - N) {
matCap[i][j] = 1;
G[i].push_back (j);
G[j].push_back (i);
}
int tmpflow;
for (; BF (); )
{
for (VIT it = G[D].begin (); it != G[D].end (); it++) {
nod = *it;
dad[D] = nod;
tmpflow = inf;
for (int i = D; i != S; i = dad[i])
tmpflow = min (tmpflow, matCap[dad[i]][i] - f[dad[i]][i]);
if (tmpflow == 0)
continue;
for (int i = D; i != S; i = dad[i]) {
f[dad[i]][i] += tmpflow;
f[i][dad[i]] -= tmpflow;
}
}
}
for (int i = 1; i <= N; i++)
for (int j = N + 1; j <= (N << 1) + 1; j++)
if (i != j - N && f[i][j] == 1)
sol.push_back (make_pair (i, j - N));
printf ("%d\n", sol.size ());
for (int i = 0; i < sol.size (); i++)
printf ("%d %d\n", sol[i].first, sol[i].second);
return 0;
}