Pagini recente » Cod sursa (job #869071) | Cod sursa (job #2261288) | Cod sursa (job #1937638) | Profil alexandrina_alexandrina | Cod sursa (job #2054412)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#ifdef INFOARENA
#define ProblemName "harta"
#endif
#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif
const int MAXN = 210;
vector<int> G[MAXN];
int N;
struct edge {
int u, C;
edge(int uu, int cc) : u(uu), C(cc) {}
};
vector<edge> edges;
inline void addEdge(int v, int u, int c) {
G[v].push_back((int)edges.size());
edges.push_back(edge(u, c));
G[u].push_back((int)edges.size());
edges.push_back(edge(v, 0));
}
int nedge[MAXN], dst[MAXN], Q[MAXN];
int _;
int ql, qr;
#define INFINIT 0x3F3F3F3F
bool BFS(int s) {
memset(dst, 0x3F, sizeof(dst));
dst[s] = 0;
ql = 0, qr = 1;
while ((ql < qr) && (dst[N - 1] == INFINIT)) {
int t = Q[ql++];
for (int i = 0; i != (int)G[t].size(); ++i) {
int edgeID = G[t][i];
int u = edges[edgeID].u;
if (!edges[edgeID].C) continue;
if (dst[u] != INFINIT) continue;
dst[u] = dst[t] + 1;
Q[qr++] = u;
}
}
return (dst[N - 1] != INFINIT);
}
int DFS(int v, int flow) {
if (v == (N - 1)) return flow;
for (; nedge[v] != (int)G[v].size(); ++nedge[v]) {
int edgeID = G[v][nedge[v]];
int u = edges[edgeID].u;
if (!edges[edgeID].C) continue;
if (dst[v] + 1 != dst[u]) continue;
int actualFlow = DFS(u, min(edges[edgeID].C, flow));
if (actualFlow == 0) continue;
edges[edgeID].C -= actualFlow;
edges[edgeID ^ 1].C += actualFlow;
return actualFlow;
}
return 0;
}
int blockingFlow() {
int totalFlow = 0;
memset(nedge, 0, sizeof(nedge));
int flow = 0;
while ((flow = DFS(0, INFINIT))) totalFlow += flow;
return totalFlow;
}
int Dinic() {
int flow = 0;
while (BFS(0)) flow += blockingFlow();
return flow;
}
void input() {
int n;
scanf("%d", &n);
N = 2 * n + 2;
for (int i = 0; i < n; ++i) {
int inp, out;
scanf("%d%d", &inp, &out);
addEdge(0, 1 + i, inp);
addEdge(1 + n + i, 2 * n + 1, out);
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (i != j)
addEdge(1 + i, 1 + n + j, 1);
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OuFile, "w", stdout));
input();
int f = Dinic();
printf("%d\n", f);
int n = (N - 2) / 2;
for (int i = 1; i <= n; ++i)
for (const auto &e : G[i]) {
if (edges[e ^ 1].C == 0)
continue;
int j = edges[e].u - (1 + n);
if (j < 0 || j >= n)
continue;
printf("%d %d\n", i, j + 1);
}
return 0;
}