Pagini recente » Cod sursa (job #1224599) | Cod sursa (job #1323470) | Cod sursa (job #2697149) | Cod sursa (job #2113664) | Cod sursa (job #2961821)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<vector<int>> la;
int cap[201][201], *tata, s, t,n, *viz;
bool bfs(){
viz = new int[t];
queue<int> coada;
coada.push(s);
viz[s]=1;
tata[s]=-1;
while(!coada.empty()){
int act;
act=coada.front();
coada.pop();
for(auto vecin:la[act]){
if(viz[vecin]==0 && cap[act][vecin]!=0){
tata[vecin] = act;
if(act == vecin)
return 1;
viz[vecin]=1;
coada.push(vecin);
}
}
}
return 0;
}
int EdomondsKarp(){
long fluxmax = 0;
while(bfs()==true){
int u, v=t;
int flux = INT_MAX;
while(v!=s){
u=tata[v];
if(cap[u][v]<flux){
flux=cap[u][v];
}
v=tata[v];
}
v=t;
while(v!=s){
u=tata[v];
cap[v][u]+=flux;
cap[u][v]-=flux;
v=tata[v];
}
fluxmax+=flux;
}
return fluxmax;
}
int main() {
f>>n;
s = 0;
t = 2*n+1;
la.resize(201);
tata = new int[2*n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j){
la[i].push_back(j+n);
la[j+n].push_back(i);
cap[i][j+n]=1;
}
}
}
for(int i=1;i<=n;i++){
int x, y;
f>>x>>y;
la[s].push_back(i);
la[i].push_back(s);
cap[s][i] = x;
la[t].push_back(i+n);
la[i+n].push_back(t);
cap[i+n][t]=y;
}
/*
for(int i=1;i<=n+n;i++){
for(int j=1;j<=n+n;j++){
cout<<la[i][j]<<" ";
}
cout<<endl;
}
*/
g<<EdomondsKarp()<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(cap[j+n][i]==1){
g<<i<<" "<<j<<endl;
}
}
}
return 0;
}