Pagini recente » Cod sursa (job #583613) | Cod sursa (job #2569242) | Cod sursa (job #1580833) | Cod sursa (job #2372237) | Cod sursa (job #3189371)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int INF = 1e9;
int n;
int capacity[202][202];
int parent[202];
bool bfs() {
memset(parent, -1, sizeof(parent));
queue<pair<int, int>> q;
q.push({0, INF});
parent[0] = 0;
while (!q.empty()) {
int currentNode = q.front().first;
int flow = q.front().second;
q.pop();
for (int nextNode = 0; nextNode <= 2 * n + 1; ++nextNode) {
if (parent[nextNode] == -1 && capacity[currentNode][nextNode] > 0) {
parent[nextNode] = currentNode;
int newFlow = min(flow, capacity[currentNode][nextNode]);
if (nextNode == 2 * n + 1) {
for (int node = nextNode; node != 0; node = parent[node]) {
capacity[parent[node]][node] -= newFlow;
capacity[node][parent[node]] += newFlow;
}
return true;
}
q.push({nextNode, newFlow});
}
}
}
return false;
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++i) {
int out, in;
fin >> out >> in;
capacity[0][i] = out;
capacity[n + i][2 * n + 1] = in;
for (int j = 1; j <= n; ++j) {
if (i != j) {
capacity[i][n + j] = 1;
}
}
}
int maxFlow = 0;
while (bfs()) {
++maxFlow;
}
fout << maxFlow << '\n';
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (capacity[i][n + j] == 0 && i != j) {
fout << i << ' ' << j << '\n';
}
}
}
return 0;
}