Pagini recente » Cod sursa (job #1219901) | Cod sursa (job #1106201) | Cod sursa (job #576803) | Cod sursa (job #126401) | Cod sursa (job #161408)
Cod sursa(job #161408)
#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <climits>
#include <queue>
#define NMAX 256
using namespace std;
int Cap[NMAX][NMAX], n;
int From[NMAX], ord;
bool Used[NMAX];
queue<int> Q;
int breadthFirst(int src, int snk) {
int i;
for (i = 0; i <= snk; ++ i) {
From[i] = -1;
Used[i] = false;
}
for (; Q.empty() == false; Q.pop())
;
Used[src] = true;
int cur;
bool stop = false;
for (Q.push(src); Q.empty() == false && stop == false; Q.pop()) {
cur = Q.front();
for (i = 0; i <= snk; ++ i)
if (Cap[cur][i] > 0 && Used[i] == false) {
Used[i] = true;
From[i] = cur;
Q.push(i);
if (i == snk) {
stop = true;
break;
}
}
}
int pathCap = INT_MAX;
for (cur = snk; From[cur] != -1; cur = From[cur]) {
//printf("%d ", cur);
pathCap = min(pathCap, Cap[From[cur]][cur]);
//printf("%d\n", pathCap);
}
if (pathCap == INT_MAX)
return 0;
//printf("%d\n", pathCap);
for (cur = snk; From[cur] != -1; cur = From[cur]) {
Cap[From[cur]][cur] -= pathCap;
Cap[cur][From[cur]] += pathCap;
}
return pathCap;
}
void printCap() {
int i, j, snk = 2 * n + 1;
printf("%d\n", ord);
for (i = 0; i <= snk; ++ i) {
for (j = 0; j <= snk; ++ j)
printf("%d ", Cap[i][j]);
printf("\n");
}
}
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &n);
int i, snk = 2 * n + 1;
for (i = 1; i <= n; ++ i)
scanf("%d %d", &Cap[0][i], &Cap[i + n][snk]);
int j;
for (i = 1; i <= n; ++ i)
for (j = 1; j <= n; ++ j)
if (i != j)
Cap[i][j + n] = 1;
int pathCap, ans = 0;
for (ord = 1, pathCap = breadthFirst(0, snk); pathCap != 0; pathCap = breadthFirst(0, snk), ++ ord) {
ans += pathCap;
//printCap();
}
printf("%d\n", ans);
for (i = 1; i <= n; ++ i)
for (j = n + 1; j < snk; ++ j)
if (Cap[j][i] > 0)
printf("%d %d\n", i, j - n);
return 0;
}