Pagini recente » Cod sursa (job #2834572) | Cod sursa (job #2230906) | Cod sursa (job #162273) | Cod sursa (job #2264966) | Cod sursa (job #3302466)
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#define endl '\n'
#endif
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
template<typename T>
bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }
template<typename T>
bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
constexpr int NMAX = 105;
constexpr int INF = 1e9+5;
struct FlowGraph {
struct Node {
int y, cap, rev;
};
const int S = 0, T = 1;
vector<int> dist, idx;
vector<vector<Node>> g;
FlowGraph() {
add_node();
add_node();
}
int add_node() {
dist.push_back(0);
idx.push_back(0);
g.emplace_back();
return sz(g) - 1;
}
void add_edge(int x, int y, int cap) {
g[x].emplace_back(y, cap, sz(g[y]));
g[y].emplace_back(x, 0, sz(g[x]) - 1);
}
bool bfs() {
fill(all(dist), INF);
fill(all(idx), 0);
queue<int> q;
dist[S] = 0;
q.push(S);
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto &[ y, cap, _ ] : g[x]) {
if (cap && ckmin(dist[y], dist[x] + 1)) {
q.push(y);
}
}
}
return dist[T] != INF;
}
int dfs(const int x, const int flow = INF) {
if (x == T) return flow;
for (; idx[x] < sz(g[x]); idx[x]++) {
auto &[ y, cap, rev ] = g[x][idx[x]];
if (cap && dist[y] == dist[x] + 1) {
if (const int f = dfs(y, min(flow, cap))) {
cap -= f;
g[y][rev].cap += f;
return f;
}
}
}
return 0;
}
int compute() {
int max_flow = 0;
while (bfs()) {
while (const int flow = dfs(S)) {
max_flow += flow;
}
}
return max_flow;
}
};
int n;
int in[NMAX], out[NMAX];
vector<int> g[NMAX];
int l[NMAX], r[NMAX];
int val[NMAX];
void read() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> out[i] >> in[i];
}
}
void solve() {
FlowGraph f;
int m = 0;
for (int i = 1; i <= n; i++) {
l[i] = f.add_node();
r[i] = f.add_node();
val[r[i]] = i;
f.add_edge(f.S, l[i], out[i]);
f.add_edge(r[i], f.T, in[i]);
m += in[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j) {
f.add_edge(l[i], r[j], 1);
}
}
}
assert(f.compute() == m);
cout << m << endl;
for (int x = 1; x <= n; x++) {
for (auto &[ y, cap, _] : f.g[l[x]]) {
if (!cap && y != f.S) {
cout << x << ' ' << val[y] << endl;
out[x]--;
in[val[y]]--;
}
}
}
for (int i = 1; i <= n; i++) {
assert(in[i] == 0);
assert(out[i] == 0);
}
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#else
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
solve();
return 0;
}