Pagini recente » Cod sursa (job #1846603) | Cod sursa (job #2084934) | Cod sursa (job #1754105) | Cod sursa (job #1104559) | Cod sursa (job #319781)
Cod sursa(job #319781)
#include <cstdio>
#include <cstring>
#include <vector>
#define maxn 110
using namespace std;
int c[2 * maxn][2 * maxn], flux[2 * maxn], up[2 * maxn];
int i, j, n, sink, dest, ok, futot, a, b;
vector <pair<int, int> > sol;
vector <pair<int, int> >::iterator it;
void init() {
ok = 0;
memset(flux, 0, sizeof(flux));
memset(up, -1, sizeof(up));
flux[sink] = 2000000000;
}
inline int min(int a, int b) {
if (a < b)
return a;
return b;
}
void bf() {
int p, u, cd[2 * maxn];
int i, nod, ant;
p = u = 1;
cd[1] = sink;
while (p <= u) {
nod = cd[p];
for (i = 1; i <= 2 * n + 2; i++)
if (c[nod][i] && flux[i] == 0) {
u++;
cd[u] = i;
flux[i] = min(c[nod][i], flux[nod]);
up[i] = nod;
if (i == dest) {
p = u + 1;
break;
}
}
p++;
}
/* for (i = 1; i <= u; i++)
fprintf(stderr, "%d ", cd[i]);
fprintf(stderr, "\n");*/
// fprintf(stderr, "%d\n", flux[dest]);
ok = flux[dest];
if (ok) {
nod = dest;
while (nod != sink) {
ant = up[nod];
c[ant][nod] -= flux[dest];
c[nod][ant] += flux[dest];
nod = ant;
}
}
}
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &n);
//fac sursa 2*N+1 si destinatia 2*N+2
sink = 2 * n + 1;
dest = 2 * n + 2;
for (i = 1; i <= n; i++) {
scanf("%d%d", &a, &b);
c[sink][i] = c[i][sink] = b;
c[i + n][dest] = c[dest][i + n] = a;
}
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i != j)
c[i][j + n] = 1;
ok = 1;
while (ok) {
init();
bf();
// fprintf(stderr, "%d\n", flux[dest]);
}
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i != j && c[i][j + n] == 0)
sol.push_back(make_pair(j, i));
printf("%d\n", sol.size());
for (it = sol.begin(); it != sol.end(); ++it)
printf("%d %d\n", it->first, it->second);
return 0;
}