Pagini recente » Cod sursa (job #2211328) | Cod sursa (job #455554) | Cod sursa (job #1119686) | Cod sursa (job #2512066) | Cod sursa (job #3190176)
#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;
#define NX 210
class MaxFlow {
private:
int S, T, N, flow;
vector<vector<int>> cap;
vector<int> pi;
queue<int> Q;
public:
MaxFlow() : S(0), T(0), N(0), flow(0) {}
void readInput() {
int i, j;
cin >> N;
S = 0;
T = 2 * N + 1;
cap.resize(NX, vector<int>(NX, 0));
pi.resize(NX, -1);
for (i = 1; i <= N; i++) {
cin >> cap[i + N][T] >> cap[0][i];
}
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
if (i != j) {
cap[i][j + N] = 1;
}
}
}
N = T;
}
int minVal(int x, int y) {
return x < y ? x : y;
}
void augment() {
int i, bot, u, v, z;
while (true) {
fill(pi.begin(), pi.end(), -1);
pi[S] = -2;
while (!Q.empty()) {
Q.pop();
}
Q.push(S);
while (!Q.empty() && pi[T] == -1) {
u = Q.front();
Q.pop();
for (i = 0; i <= N; i++) {
if (cap[u][i] && pi[i] == -1) {
pi[i] = u;
Q.push(i);
}
}
}
if (pi[T] == -1) {
break;
}
for (z = 0; z <= N; z++) {
if (cap[z][T] && pi[z] != -1) {
bot = cap[z][T];
for (u = pi[z], v = z; u >= 0; v = u, u = pi[u]) {
bot = minVal(bot, cap[u][v]);
}
if (bot <= 0) {
continue;
}
cap[z][T] -= bot;
cap[T][z] += bot;
for (u = pi[z], v = z; u >= 0; v = u, u = pi[u]) {
cap[u][v] -= bot;
cap[v][u] += bot;
}
flow += bot;
}
}
}
}
void printOutput() {
int i, j, k = 0;
cout << flow << endl;
N >>= 1;
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
if (cap[i][j + N] == 0 && i != j) {
cout << j << " " << i << endl;
k++;
}
}
}
assert(k == flow);
}
void solve() {
readInput();
augment();
printOutput();
}
};
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
MaxFlow maxFlow;
maxFlow.solve();
return 0;
}