Pagini recente » Cod sursa (job #1218602) | Cod sursa (job #1096878) | Cod sursa (job #2939043) | Cod sursa (job #1430471) | Cod sursa (job #2962702)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define cin f
#define cout g
int n, m;
vector<int> prevs(202);
vector<vector<int>> capacity(202, vector<int>(202));
vector<vector<int>> adj(202);
int bfs(int s, int t, vector<int>& prevs) {
fill(prevs.begin(), prevs.end(), -1);
prevs[s] = -2;
queue<pair<int, int>> q;
q.push({s, INT_MAX});
while (!q.empty()) {
int curr = q.front().first;
int flow = q.front().second;
q.pop();
for (int next : adj[curr]) {
if (prevs[next] == -1 && capacity[curr][next]) {
prevs[next] = curr;
int new_flow = min(flow, capacity[curr][next]);
if (next == t)
return new_flow;
q.push({next, new_flow});
}
}
}
return 0;
}
int maxflow(int s, int t) {
int flow = 0;
int new_flow;
while (new_flow = bfs(s, t, prevs)) {
flow += new_flow;
int curr = t;
while (curr != s) {
int prev = prevs[curr];
capacity[prev][curr] -= new_flow;
capacity[curr][prev] += new_flow;
curr = prev;
}
}
return flow;
}
int main() {
cin >> n;
int sink = 2 * n + 1;
for(int i = 1; i <= n; i ++) {
int a, b;
cin >> a >> b;
adj[0].push_back(i);
adj[i].push_back(0);
capacity[0][i] = a;
adj[n+i].push_back(sink);
adj[sink].push_back(n+i);
capacity[n+i][sink] = b;
}
for (int i = 1; i<= n; i++){
for (int j = n + 1; j < sink; j++){
if (j - i == n) continue;
adj[j].push_back(i);
adj[i].push_back(j);
capacity[i][j] = 1;
}
}
cout << maxflow(0, sink) << '\n';
for (int i = 1; i <= n; i++){
for (int j = n + 1; j < sink; j++){
if (capacity[j][i] == 1)
cout << i << ' ' << j - n << '\n';
}
}
return 0;
}