Pagini recente » Utilizatori inregistrati la ONIS 2015, Runda 3 | Cod sursa (job #3210034) | Cod sursa (job #3287760) | Cod sursa (job #1548806) | Cod sursa (job #3262805)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <queue>
#define debug(x) #x << " = " << x << '\n';
using ll = long long;
#define int ll
const int INF = 1e18;
struct Dinic {
struct Edge {
int to, flow, cap;
};
int n;
std::vector<Edge> e;
std::vector<std::vector<int>> g;
std::vector<int> dist;
int source, sink;
Dinic() {}
Dinic(int _n) {
n = _n;
g.resize(n + 1);
dist.resize(n + 1);
}
void add_edge(int u, int v, int cap) {
e.push_back({v, 0, cap});
e.push_back({u, 0, 0});
g[u].push_back((int) e.size() - 2);
g[v].push_back((int) e.size() - 1);
}
bool can_bfs() {
std::queue<int> q;
dist.assign(n + 1, INF);
q.push(source);
dist[source] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto &ind : g[u]) {
auto &[v, flow, cap] = e[ind];
if (flow < cap && dist[u] + 1 < dist[v]) {
dist[v] = 1 + dist[u];
q.push(v);
}
}
}
return dist[sink] != INF;
}
int do_push(int u, int F) {
if (u == sink) {
return F;
}
int pushed = 0;
for (const auto &ind : g[u]) {
auto &[v, flow, cap] = e[ind];
if (dist[u] + 1 == dist[v] && flow < cap) {
int push = do_push(v, std::min(F, cap - flow));
pushed += push;
flow += push;
e[ind ^ 1].flow -= push;
F -= push;
}
}
return pushed;
}
int max_flow(int _source, int _sink) {
source = _source;
sink = _sink;
int answer = 0;
while (can_bfs()) {
int push = do_push(source, INF);
answer += push;
if (push == 0) {
break;
}
}
return answer;
}
};
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#else
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
#endif
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin >> n;
std::vector<int> in(n + 1), out(n + 1);
int m = 0;
for (int i = 1; i <= n; i++) {
std::cin >> in[i] >> out[i];
m += in[i];
}
Dinic F(2 * n + 2);
for (int i = 1; i <= n; i++) {
F.add_edge(0, i, in[i]);
F.add_edge(i + n, 2 * n + 1, out[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j) {
F.add_edge(i, j + n, 1);
}
}
}
std::cout << F.max_flow(0, 2 * n + 1) << '\n';
int id = 4 * n - 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
id += 2;
if (F.e[id].flow == 1) {
std::cout << i + 1 << ' ' << j + 1 << '\n';
}
}
}
}
return 0;
}