Pagini recente » Cod sursa (job #2026672) | Cod sursa (job #1263161) | Cod sursa (job #1333159) | Cod sursa (job #2247419) | Cod sursa (job #2961593)
/*
Am aplicat algoritmul Edmonds-Karp avand complexitatea O(n * m * m):
-> Parcurg graful prin bfs (cautand lanturi intre 1 si n, retinand si arborele bfs)
-> ma plimb din parinte in parinte pana ajung la 1 pentru a calcula minimul (locul care imi da bottleneck in lant)
*/
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,m,k;
vector< vector<int > > edges;
int cap[20005][20005];
vector<int> arb;
vector<int> vis;
int maxFlow;
bool bfs(){
fill(arb.begin(), arb.end(),0);
fill(vis.begin(), vis.end(),0);
arb[0] = 0;
vis[0] = 1;
queue<int> q;
q.push(0);
while(!q.empty()){
int curr = q.front();
q.pop();
if(curr == 2*n+1)
return true;
for(int i = 0; i < edges[curr].size(); ++i){
if(vis[edges[curr][i]] == 0 && cap[curr][edges[curr][i]] > 0){
arb[edges[curr][i]] = curr;
vis[edges[curr][i]] = 1;
q.push(edges[curr][i]);
}
}
}
return false;
}
int main(){
fin >> n;
edges.resize(n*2+2);
arb.resize(n*2+2);
vis.resize(n*2+2);
int a,b;
for(int i = 1; i <= n; ++i){
fin >> a >> b;
edges[i].push_back(0);
edges[0].push_back(i);
edges[n+i].push_back(2*n+1);
edges[2*n+1].push_back(n+i);
cap[0][i] = a;
cap[i+n][2*n+1] = b;
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(i != j){
edges[i].push_back(j+n);
edges[j+n].push_back(i);
cap[i][n+j] = 1;
}
}
}
while(bfs()){
for(int i = 0; i < edges[2*n+1].size(); ++i){
if(vis[edges[2*n+1][i]] == 1){
int fl = INT_MAX;
arb[2*n+1] = edges[2*n+1][i];
for(int j = 2*n+1; j != 0; j = arb[j]){
fl = min(fl, cap[arb[j]][j]);
}
if(fl != 0){
for(int j = 2*n+1; j != 0; j = arb[j]){
cap[arb[j]][j] -= fl;
cap[j][arb[j]] += fl;
}
maxFlow += fl;
}
}
}
}
fout << maxFlow << '\n';
for(int i = 1; i <= n; ++i){
for(int j = 1; j < edges[i].size(); ++j){
if(cap[i][edges[i][j]] == 0){
fout << i << ' ' << edges[i][j] - n << '\n';
}
}
}
}