Pagini recente » Cod sursa (job #2655699) | Cod sursa (job #2720187) | Cod sursa (job #2691932) | Cod sursa (job #161204) | Cod sursa (job #2379203)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210;
const int source = 0;
const int target = 201;
int capacity[MAXN][MAXN];
int currentFlow[MAXN][MAXN];
vector< int > gr[MAXN];
int indeg[MAXN], outdeg[MAXN];
int d[MAXN];
inline void addEdge(int a, int b, int c) {
gr[a].emplace_back(b);
capacity[a][b] += c;
}
bool bfs() {
memset(d, 0, sizeof d);
queue< int > q;
q.push(source);
while(q.size()) {
int node = q.front();
q.pop();
if(node == target) return true;
for(auto &x : gr[node]) {
if(!d[x] && currentFlow[node][x] < capacity[node][x]) {
d[x] = d[node] + 1;
q.push(x);
}
}
}
return false;
}
int dfs(int node, int flow) {
if(node == target) return flow;
if(!flow) return 0;
int current = 0;
for(auto &x : gr[node]) {
if(d[x] != d[node] + 1) continue;
auto pa = dfs(x, min(flow, capacity[node][x] - currentFlow[node][x]));
currentFlow[node][x] += pa;
currentFlow[x][node] -= pa;
flow -= pa;
current += pa;
}
return current;
}
int main () {
ifstream f("harta.in");
ofstream g("harta.out");
int n;
f >> n;
for(int i = 1; i <= n; ++i) {
f >> outdeg[i] >> indeg[i];
addEdge(source, i, outdeg[i]);
addEdge(i + 100, target, indeg[i]);
for(int j = 1; j <= 100; ++j) {
if(i == j) continue;
addEdge(i, 100+j, 1);
addEdge(100+j, i, 0);
}
}
int ans = 0;
while(bfs()) {
ans += dfs(source, 1e9);
}
g << ans << '\n';
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(currentFlow[i][100+j]) g << i << ' ' << j << '\n';
}
}
return 0;
}