Pagini recente » Cod sursa (job #2229194) | Cod sursa (job #747521) | Cod sursa (job #675187) | Istoria paginii info-oltenia-2018/individual/10 | Cod sursa (job #3188878)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int INF = 1e9;
struct Edge {
int x;
int flow;
int cap;
int nxt;
};
struct Dinic {
int source;
int sink;
int n;
vector <vector <Edge>> gr;
vector <int> dist;
vector <int> start;
Dinic(int _source, int _sink, int _size) {
source = _source;
sink = _sink;
n = _size;
gr.resize(_size);
dist.resize(_size);
start.resize(_size);
}
void add_edge(int x, int y, int cap) {
gr[x].push_back({y, 0, cap, (int)gr[y].size()});
gr[y].push_back({x, 0, 0, (int)gr[x].size() - 1});
}
bool bfs() {
for (int i = 0; i < n; i++)
dist[i] = -1;
dist[source] = 0;
queue <int> q;
q.push(source);
while (q.size()) {
int node = q.front();
q.pop();
for (auto vec : gr[node]) {
if (dist[vec.x] == - 1 && vec.cap > vec.flow) {
dist[vec.x] = dist[node] + 1;
q.push(vec.x);
}
}
}
return dist[sink] != -1;
}
int dfs(int node, int sink, int flow) {
if (node == sink)
return flow;
while (start[node] < gr[node].size()) {
Edge e = gr[node][start[node]];
if (dist[e.x] == dist[node] + 1 && e.flow < e.cap) {
int new_flow = dfs(e.x, sink, min(flow, e.cap - e.flow));
if (new_flow > 0) {
gr[node][start[node]].flow += new_flow;
gr[e.x][e.nxt].flow -= new_flow;
return new_flow;
}
}
start[node]++;
}
return 0;
}
int maxflow() {
int ans = 0;
while (bfs()) {
int flow;
for (auto &x : start) x = 0;
while (flow = dfs(source, sink, INF))
ans += flow;
}
return ans;
}
vector <pair <int, int>> get_edges() {
vector <pair <int, int>> ans;
int sz = (n - 2) / 2;
for (int i = 0; i < sz; i++) {
for (auto vec : gr[i]) {
if (vec.flow == 1) {
ans.push_back({i, vec.x});
}
}
}
return ans;
}
};
int main () {
freopen ("harta.in", "r", stdin);
freopen ("harta.out", "w", stdout);
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int n;
cin >> n;
int source = 2 * n, sink = 2 * n + 1;
Dinic network (source, sink, 2 * n + 2);
for (int i = 0; i < n; i++) {
for (int j = n; j < 2 * n; j++) {
if (i != j - n)
network.add_edge (i, j, 1);
}
}
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
network.add_edge (source, i, x);
network.add_edge (i + n, sink, y);
}
cerr << network.maxflow() << "\n";
auto ans = network.get_edges();
cout << ans.size() << "\n";
for (auto it : ans)
cout << it.first + 1 << " " << it.second - n + 1 << "\n";
return 0;
}