Pagini recente » Cod sursa (job #1503063) | Cod sursa (job #2342870) | Cod sursa (job #483204) | Cod sursa (job #3237074) | Cod sursa (job #3262791)
#pragma GCC optimize("Ofast")
#ifndef LOCAL
#include <bits/stdc++.h>
#define endl '\n'
#else
#include <iostream>
#endif
using namespace std;
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
const int NMAX = 105;
const int INF = 2e9+5;
struct Dinic {
struct Edge {
int x, cap, other;
};
int n;
vector<vector<Edge>> e;
vector<int> dist, last;
int S, T;
Dinic() {
S = add_node();
T = add_node();
}
int add_node() {
e.emplace_back();
dist.emplace_back();
last.emplace_back();
return sz(e) - 1;
}
void add_edge(int x, int y, int cap) {
e[x].push_back({ y, cap, sz(e[y]) });
e[y].push_back({ x, 0, sz(e[x]) - 1 });
}
bool bfs() {
fill(all(dist), INF);
fill(all(last), 0);
queue<int> q;
q.push(S);
dist[S] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto &[ u, cap, _ ] : e[x]) {
if (cap && dist[u] == INF) {
dist[u] = dist[x] + 1;
q.push(u);
}
}
}
return dist[T] != INF;
}
int dfs(int x, int flow = INF) {
if (flow == 0) return 0;
if (x == T) return flow;
for (; last[x] < sz(e[x]); last[x]++) {
int i = last[x];
auto &it = e[x][i];
if (it.cap && dist[it.x] == dist[x] + 1) {
if (int f = dfs(it.x, min(flow, it.cap))) {
it.cap -= f;
e[it.x][it.other].cap += f;
return f;
}
}
}
return 0;
}
int max_flow() {
int flow = 0;
while (bfs()) {
while (int f = dfs(S)) {
flow += f;
}
}
return flow;
}
};
int n, m;
int out[NMAX], in[NMAX];
int a[NMAX], b[NMAX];
int bval[NMAX];
void read() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> out[i] >> in[i];
}
}
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(0);
cout.tie(0);
read();
Dinic d;
for (int i = 1; i <= n; i++) {
a[i] = d.add_node();
d.add_edge(d.S, a[i], out[i]);
b[i] = d.add_node();
bval[b[i]] = i;
d.add_edge(b[i], d.T, in[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j) {
d.add_edge(a[i], b[j], 1);
}
}
}
cout << d.max_flow() << endl;
for (int i = 1; i <= n; i++) {
for (auto &[ j, cap, _ ] : d.e[a[i]]) {
if (j != d.S && cap == 0) {
cout << i << ' ' << bval[j] << endl;
}
}
}
return 0;
}