Pagini recente » Cod sursa (job #2809019) | Cod sursa (job #2507456) | Cod sursa (job #615458) | Cod sursa (job #1536674) | Cod sursa (job #2589781)
#include <cstdio>
#include <queue>
using namespace std;
const int N = 300 + 7;
vector<int> g[N];
int s;
int d;
int l[N];
struct Edge {
int to;
int cost;
};
vector<Edge> edges;
void add(int a, int b, int c) {
g[a].push_back((int) edges.size());
edges.push_back({b, c});
g[b].push_back((int) edges.size());
edges.push_back({a, c});
}
bool bfs() {
queue<int> q;
for (int i = 1; i <= d; i++) {
l[i] = -1;
}
l[s] = 0;
q.push(s);
while (!q.empty()) {
int a = q.front();
q.pop();
for (auto &i : g[a]) {
int b = edges[i].to;
if (edges[i].cost > 0 && l[b] == -1) {
l[b] = 1 + l[a];
q.push(b);
}
}
}
return l[d] != -1;
}
int dfs(int a, int cap) {
if (a == d || cap == 0) {
return cap;
}
for (auto &i : g[a]) {
int b = edges[i].to;
int co = edges[i].cost;
if (co > 0 && l[b] == 1 + l[a]) {
int val = dfs(b, min(cap, co));
if (val > 0) {
edges[i].cost -= val;
edges[i ^ 1].cost += val;
return val;
}
}
}
return 0;
}
int main() {
freopen ("harta.in", "r", stdin);
freopen ("harta.out", "w", stdout);
int n;
scanf("%d", &n);
s = 1;
d = 2 * n + 2;
for (int i = 1; i <= n; i++) {
int out, in;
scanf("%d %d", &out, &in);
add(s, i + 1, in);
add(i + n + 1, d, out);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j) {
add(i + 1, j + n + 1, 1);
}
}
}
while (bfs()) {
while (dfs(s, (int) 1e9)) {
}
}
vector<pair<int, int>> sol;
for (int i = 1; i <= n; i++) {
for (auto &id : g[i + 1]) {
int j = edges[id].to - n - 1;
int co = edges[id].cost;
if (co == 0 && 1 <= j && j <= n) {
sol.push_back({i, j});
}
}
}
printf("%d\n", (int) sol.size());
for (auto &it : sol) {
printf("%d %d\n", it.first, it.second);
}
}