Pagini recente » Cod sursa (job #331155) | Cod sursa (job #2128909) | Cod sursa (job #3004666) | Cod sursa (job #2081865) | Cod sursa (job #3186093)
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<vector<int>> capacitate;
vector<vector<int>> flux;
vector<bool> viz;
vector<int> tata;
bool BFS(int s, int t){
queue<int> q;
q.push(s);
while(!q.empty()){
int nod = q.front();
q.pop();
if(viz[nod])
continue;
viz[nod] = true;
for(int i=0; i<t+1; i++){
if(!viz[i] && capacitate[nod][i] - flux[nod][i] > 0){
q.push(i);
tata[i] = nod;
}
}
}
return viz[t];
}
int main() {
int n;
fin>>n;
tata.resize(2*n+2, -1);
viz.resize(2*n+2, false);
flux.resize(2*n+2, vector<int>(2*n+2, 0));
capacitate.resize(2*n+2, vector<int>(2*n+2, 0));
int s = 2*n, t=2*n+1;
for(int i=0; i<n; i++){
int x, y;
fin >> x >> y;
capacitate[s][i] = x;
capacitate[n+i][t] = y;
for(int j=0; j<n; j++)
if(i != j)
capacitate[i][n+j] = 1;
}
int flux_maxim = 0;
while(BFS(s, t)){
int cap_minima = INT_MAX;
int nod1 = tata[t], nod2 = t;
while(nod1 != -1){
int cap = capacitate[nod1][nod2] - flux[nod1][nod2];
if(cap < cap_minima)
cap_minima = cap;
nod2 = nod1;
nod1 = tata[nod1];
}
nod1 = tata[t], nod2 = t;
while(nod1 != -1){
flux[nod1][nod2] += cap_minima;
flux[nod2][nod1] -= cap_minima;
nod2 = nod1;
nod1 = tata[nod1];
}
flux_maxim += cap_minima;
for(int i=0; i<2*n+2; i++) {
viz[i] = false;
}
}
fout<<flux_maxim<<endl;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++){
if(flux[i][n+j] == 1) {
fout<<i+1<<' '<<j+1<<endl;
}
}
return 0;
}