Pagini recente » Cod sursa (job #2553467) | Cod sursa (job #2115958)
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 105;
vector< int > gr[MaxN];
int capacity[MaxN][MaxN];
int current_flow[MaxN][MaxN];
int boss[MaxN];
bool viz[MaxN];
bool can_push(int source, int target){
memset(boss, 0, sizeof boss);
memset(viz, 0, sizeof viz);
queue< int > q;
q.push(source);
while(q.size()){
int node = q.front();
q.pop();
if(node == target) continue;
for(auto x : gr[node]){
if(viz[x] == 0 && current_flow[node][x] < capacity[node][x]){
boss[x] = node;
viz[x] = true;
q.push(x);
}
}
}
return viz[target];
}
void update_flow(int source, int target, int & ans){
for(auto x : gr[target]){
if(boss[x] == 0) continue;
boss[target] = x;
int node = target;
int minimum_flow = 1<<30;
while(node != source){
minimum_flow = min(minimum_flow, capacity[ boss[node] ][node] - current_flow[ boss[node] ][node]);
node = boss[node];
}
node = target;
while(node != source){
current_flow[ boss[node] ][node] += minimum_flow;
current_flow[node][ boss[node] ] -= minimum_flow;
node = boss[node];
}
ans += minimum_flow;
}
}
int main(){
ifstream f("harta.in");
ofstream g("harta.out");
int n;
f >> n;
int source = 0;
int target = n<<1|1;
for(int i = 1; i <= n; ++i){
int x, y;
f >> x >> y;
gr[source].push_back(i);
gr[i].push_back(source);
capacity[source][i] = x;
gr[target].push_back(n + i);
gr[n + i].push_back(target);
capacity[n + i][target] = y;
for(int j = 1; j <= n; ++j){
if(i == j) continue;
gr[i].push_back(j + n);
gr[j + n].push_back(i);
capacity[i][j + n] = 1;
}
}
int max_flow = 0;
while(can_push(source, target)) update_flow(source, target, max_flow);
g << max_flow << '\n';
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(current_flow[i][j + n]) g << i << ' ' << j << '\n';
}
}
return 0;
}