Pagini recente » Cod sursa (job #2048449) | Cod sursa (job #979613) | Cod sursa (job #2598413) | Cod sursa (job #638252) | Cod sursa (job #2586375)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
class FlowNetwork {
private:
int n, s, t;
vector<vector<int>> ad, cap;
bool bfs(vector<bool>& vis, vector<int>& father) {
fill(vis.begin(), vis.end(), false);
vis[s] = true;
queue<int> q; q.push(s);
while (!q.empty()) {
int node = q.front(); q.pop();
for (int nghb : ad[node])
if (!vis[nghb] && cap[node][nghb]) {
vis[nghb] = true;
father[nghb] = node;
if (nghb != t)
q.push(nghb);
}
}
return vis[t];
}
public:
FlowNetwork(int n, int s, int t) :
n(n), s(s), t(t), ad(n + 1),
cap(n + 1, vector<int>(n + 1)) { }
void addEdge(int x, int y, int z = 1) {
ad[x].push_back(y);
ad[y].push_back(x);
cap[x][y] = z;
}
auto maxFlow() {
vector<bool> vis(n + 1);
vector<int> father(n + 1);
int maxFlow = 0;
while (bfs(vis, father))
for (int nghb : ad[t])
if (vis[nghb] && cap[nghb][t]) {
int flow = 1e9;
father[t] = nghb;
for (int i = t; i != s; i = father[i])
flow = min(flow, cap[father[i]][i]);
for (int i = t; i != s; i = father[i]) {
cap[father[i]][i] -= flow;
cap[i][father[i]] += flow;
}
maxFlow += flow;
}
pair<int, vector<pair<int, int>>> ans;
ans.first = maxFlow;
int x = (n - 1) / 2;
for (int i = 1; i <= x; i++)
for (int j = 1; j <= x; j++)
if (cap[j + x][i])
ans.second.emplace_back(i, j);
return ans;
}
};
int main() {
int n; fin >> n;
FlowNetwork graph(2 * n + 1, 0, 2 * n + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (j != i)
graph.addEdge(i, j + n);
for (int i = 1; i <= n; i++) {
int out, in; fin >> out >> in;
graph.addEdge(0, i, out);
graph.addEdge(i + n, 2 * n + 1, in);
}
auto ans = graph.maxFlow();
fout << ans.first << '\n';
for (auto edge : ans.second)
fout << edge.first << ' ' << edge.second << '\n';
fout.close();
return 0;
}