Pagini recente » Cod sursa (job #829549) | Cod sursa (job #832439) | Cod sursa (job #591891) | Cod sursa (job #1066293) | Cod sursa (job #3333748)
# include <bits/stdc++.h>
using namespace std;
ifstream f("1.in");
ofstream g("1.out");
const int INF = 1e9;
const int MAXN = 205;
int n;
int S, D;
int level[MAXN], ptr[MAXN];
int deg_in[105], deg_out[105];
struct Edge {
int to, cap, flow, rev;
};
vector<Edge> v[MAXN];
queue<int> q;
void add_edge(int from, int to, int cap) {
Edge a = {to, cap, 0, (int)v[to].size()};
Edge b = {from, 0, 0, (int)v[from].size()};
v[from].push_back(a);
v[to].push_back(b);
}
bool bfs() {
while (!q.empty()) q.pop();
for (int i = 0; i <= D; ++i) level[i] = -1;
level[S] = 0;
q.push(S);
while (!q.empty()) {
int nod = q.front();
q.pop();
for (const auto &edge : v[nod]) {
if (edge.cap - edge.flow > 0 && level[edge.to] == -1) {
level[edge.to] = level[nod] + 1;
q.push(edge.to);
}
}
}
return level[D] != -1;
}
int dfs(int nod, int pushed) {
if (pushed == 0 || nod == D) return pushed;
for (int &cid = ptr[nod]; cid < v[nod].size(); ++cid) {
auto &edge = v[nod][cid];
if (level[nod] + 1 != level[edge.to] || edge.cap - edge.flow == 0) continue;
int tr = dfs(edge.to, min(pushed, edge.cap - edge.flow));
if (tr == 0) continue;
edge.flow += tr;
v[edge.to][edge.rev].flow -= tr;
return tr;
}
return 0;
}
void dinic() {
while (bfs()) {
for (int i = 0; i <= D; ++i) ptr[i] = 0;
while (dfs(S, INF));
}
}
int main() {
f >> n;
S = 0;
D = 2 * n + 1;
for (int i = 1; i <= n; ++i) {
f >> deg_out[i]>>deg_in[i];
}
for (int i = 1; i <= n; ++i) {
add_edge(S, i, deg_out[i]);
}
for (int i = 1; i <= n; ++i) {
add_edge(n + i, D, deg_in[i]);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i != j) {
add_edge(i, n + j, 1);
}
}
}
dinic();
vector<pair<int, int>> edges;
for (int i = 1; i <= n; ++i) {
for (const auto &edge : v[i]) {
if (edge.to > n && edge.to != D && edge.flow == 1) {
edges.push_back({i, edge.to - n});
}
}
}
g << edges.size() << '\n';
for (const auto &p : edges) {
g << p.first << " " << p.second << '\n';
}
return 0;
}