Pagini recente » Cod sursa (job #1756531) | Cod sursa (job #1005460) | Cod sursa (job #1605558) | Cod sursa (job #2003922) | Cod sursa (job #2434359)
#include <bits/stdc++.h>
using namespace std;
struct MaxFlow {
int n, source, sink, flow;
vector<int> parent;
vector<vector<int>> adj, capacity;
MaxFlow(int n_, int source_, int sink_) :
n(n_), source(source_), sink(sink_), flow(0), parent(n), adj(n),
capacity(n, vector<int>(n)) {}
void AddEdge(int u, int v, int cap) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
capacity[u][v] += cap;
}
bool CanIncreaseFlow() {
fill(parent.begin(), parent.end(), -1);
parent[source] = -2;
vector<int> q = {source};
for (int i = 0; i < (int)q.size(); ++i) {
int node = q[i];
for (int &x : adj[node]) {
if (parent[x] == -1 && capacity[node][x]) {
parent[x] = node;
q.emplace_back(x);
}
}
}
return parent[sink] != -1;
}
int GetMaxFlow() {
while (CanIncreaseFlow()) {
int node = sink;
int add_flow = (int)1e9;
while (node != source) {
add_flow = min(add_flow, capacity[parent[node]][node]);
node = parent[node];
}
node = sink;
while (node != source) {
capacity[parent[node]][node] -= add_flow;
capacity[node][parent[node]] += add_flow;
node = parent[node];
}
flow += add_flow;
}
return flow;
}
};
int main() {
ifstream cin("harta.in");
ofstream cout("harta.out");
int n; cin >> n;
MaxFlow g(2 * n + 2, 0, 2 * n + 1);
for (int i = 1; i <= n; ++i) {
int in, out; cin >> in >> out;
g.AddEdge(g.source, i, in);
g.AddEdge(i + n, g.sink, out);
for (int j = 1; j <= n; ++j) if (i != j) {
g.AddEdge(i, j + n, 1);
}
}
cout << g.GetMaxFlow() << endl;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) if (i != j) {
if (g.capacity[i][j + n] == 0) {
cout << i << ' ' << j << '\n';
}
}
}
}