Pagini recente » Cod sursa (job #546205) | Cod sursa (job #3188773)
#include<vector>
#include<tuple>
#include<queue>
#include<climits>
#include <fstream>
std::ifstream cin("harta.in");
std::ofstream cout("harta.out");
//#include <iostream>
//using namespace std;
class flux{
int n;
std::vector<std::vector<int>> cap,adi;
int BFS(int start, int stop, std::vector<int> &tata){
fill(tata.begin(),tata.end(),-1);
tata[start] = -2;
std::queue<std::pair<int,int>> q;
q.emplace(start,INT_MAX);
while(!q.empty()){
int v = q.front().first;
int f = q.front().second;
q.pop();
for(auto vecin: adi[v]){
if(tata[vecin]==-1 && cap[v][vecin]){
tata[vecin] = v;
int flux_nou = std::min(f,cap[v][vecin]);
if(vecin == stop){
return flux_nou;
}
q.emplace(vecin,flux_nou);
}
}
}
return 0;
}
public:
flux(int n,
std::vector<std::vector<int>> &cap,
std::vector<std::vector<int>> &adi):
n(n),cap(cap),adi(adi){}
int flux_maxim(int start, int stop){
int f = 0;
std::vector<int> tata(2*n+2);
int flux_nou;
flux_nou = BFS(start,stop,tata);
while(flux_nou){
f += flux_nou;
int v = stop;
while(v != start){
int ant = tata[v];
cap[ant][v] -= flux_nou;
cap[v][ant] += flux_nou;
v = ant;
}
flux_nou = BFS(start,stop,tata);
}
return f;
}
void afis(int start, int stop){
int maxi = flux_maxim(start,stop);
cout<<maxi<<"\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
if(cap[i][j+n]==0)cout<<i<<" "<<j<<"\n";
}
}
}
};
int main() {
int n;
cin>>n;
int start =0,stop = 2*n+1;
std::vector<std::vector<int>> cap,adi;
cap.resize(n*2+2,std::vector<int>(n*2+2,0));
adi.resize(n*2+2,std::vector<int>());
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) {
if(i==j)continue;
cap[i][j + n] = 1;
adi[i].push_back(j + n);
adi[j + n].push_back(i);
}
}
for(int i=1;i<=n;i++){
int x,y;
cin >> x >> y;
cap[start][i] = x;
cap[i + n][stop] =y;
adi[i].push_back(start);
adi[start].push_back(i);
adi[i + n].push_back(stop);
adi[stop].push_back(i + n);
}
flux x(n,cap,adi);
x.afis(start,stop);
return 0;
}