Pagini recente » Cod sursa (job #3359498) | Cod sursa (job #3359505)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, source, sink;
vector<vector<int>> C, G;
vector<int> parent;
vector<pair<int, int>> sol;
bool bfs(int start, int end) {
vector<bool> visited(2 * n + 2, false);
queue<int> Q;
Q.push(start);
visited[start] = true;
while (!Q.empty()) {
int node = Q.front();
Q.pop();
for (int neighbor : G[node]) {
if (!visited[neighbor] && C[node][neighbor] > 0) {
parent[neighbor] = node;
visited[neighbor] = true;
if (neighbor == end)
return true;
Q.push(neighbor);
}
}
}
return false;
}
int eKarp(int start, int end) {
int maxFlow = 0;
while (bfs(start, end)) {
int pathFlow = 2e9;
for (int v = end; v != start; v = parent[v]) {
int u = parent[v];
pathFlow = min(pathFlow, C[u][v]);
}
for (int v = end; v != start; v = parent[v]) {
int u = parent[v];
C[u][v] -= pathFlow;
C[v][u] += pathFlow;
}
maxFlow += pathFlow;
}
return maxFlow;
}
int main() {
fin >> n;
source = 0;
sink = 2 * n + 1;
C.resize(2 * n + 2, vector<int>(2 * n + 2, 0));
G.resize(2 * n + 2);
parent.resize(2 * n + 2);
for (int i = 1; i <= n; ++i) {
int x, y;
fin >> x >> y;
G[source].push_back(i);
G[i].push_back(source);
C[source][i] = x;
G[n + i].push_back(sink);
G[sink].push_back(n + i);
C[n + i][sink] = y;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i != j) {
G[i].push_back(n + j);
G[n + j].push_back(i);
C[i][n + j] = 1;
}
}
}
eKarp(source, sink);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i != j && C[n + j][i] == 1)
sol.push_back({i, j});
}
}
fout << sol.size() << "\n";
for (auto edge : sol) {
fout << edge.first << " " << edge.second << "\n";
}
return 0;
}