Pagini recente » Cod sursa (job #1718359) | Cod sursa (job #279831) | Cod sursa (job #2534423) | Cod sursa (job #2142192) | Cod sursa (job #2958069)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
struct FlowEdge {
int v, u;
long long cap, flow = 0;
FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};
class Graph {
private:
const long long flow_inf = 1e18;
vector<FlowEdge> edges;
vector<vector<int>> adj;
int n, m = 0;
int s, t;
vector<int> level, ptr;
queue<int> q;
public:
Graph(int n_, int s_, int t_): n(n_), s(s_), t(t_) {
adj.resize(n);
level.resize(n);
ptr.resize(n);
}
void add_edge(int v, int u, long long cap) {
edges.emplace_back(v, u, cap);
edges.emplace_back(u, v, 0);
adj[v].push_back(m);
adj[u].push_back(m + 1);
m += 2;
}
bool bfs() {
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : adj[v]) {
if (edges[id].cap - edges[id].flow < 1)
continue;
if (level[edges[id].u] != -1)
continue;
level[edges[id].u] = level[v] + 1;
q.push(edges[id].u);
}
}
return level[t] != -1;
}
long long dfs(int v, long long pushed) {
if (pushed == 0)
return 0;
if (v == t)
return pushed;
for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
int id = adj[v][cid];
int u = edges[id].u;
if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)
continue;
long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
if (tr == 0)
continue;
edges[id].flow += tr;
edges[id ^ 1].flow -= tr;
return tr;
}
return 0;
}
long long flow() {
long long f = 0;
while (true) {
fill(level.begin(), level.end(), -1);
level[s] = 0;
q.push(s);
if (!bfs())
break;
fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, flow_inf)) {
f += pushed;
}
}
return f;
}
vector<pair<int,int>> matching() {
vector<pair<int,int>> match;
for(auto& it: edges) {
if(it.flow == 1 && it.flow == it.cap && it.v != s && it.u != t && it.v != it.u) {
match.push_back(make_pair(it.v, it.u));
}
}
return match;
}
};
int main() {
int n;
fin >> n;
Graph dinic(n * 2 + 2, 0, n + n + 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i != j) {
dinic.add_edge(i, j + n, 1);
}
}
}
for(int x, y, i = 1; i <= n; i++) {
fin >> x >> y;
dinic.add_edge(0, i, x);
dinic.add_edge(i + n, n + n + 1, y);
}
fout << dinic.flow() << '\n';
auto rasp = dinic.matching();
for(auto &muchie: dinic.matching()) {
fout << muchie.first << ' ' << muchie.second - n << '\n';
}
return 0;
}