Pagini recente » Cod sursa (job #2414436) | Cod sursa (job #1344427) | Cod sursa (job #2931752) | Cod sursa (job #2239026) | Cod sursa (job #3190117)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n, m, s, t, pleaca, ajung, capac[202][202], flux[202][202];
vector<int> graf[202];
void constr_graf(){
s = 0, t = n * 2 + 1;
for(int nod = 1; nod <= n; nod++){
f >> pleaca >> ajung;
m += pleaca;
capac[s][nod] = pleaca;
capac[n + nod][t] = ajung;
graf[s].push_back(nod);
graf[n + nod].push_back(t);
for(int copie = n; copie <= n * 2; copie++){
if(copie - n != nod){
capac[nod][copie] = 1;
graf[nod].push_back(copie);
graf[copie].push_back(nod);
}
}
}
f.close();
}
bool constr_drum_crestere(queue<int>& coada, vector<int>& tati, vector<int>& viz){
coada.push(s);
viz[s] = 1;
while(!coada.empty()){
int nod = coada.front();
coada.pop();
for (auto vecin : graf[nod])
// lant nesaturat
if(!viz[vecin] && capac[nod][vecin] - flux[nod][vecin] > 0){
coada.push(vecin);
tati[vecin] = nod;
viz[vecin] = 1;
if(vecin == t)
return true;
}
}
return false;
}
void reviz_drum(queue<int>& coada, vector<int>& tati, vector<int>& viz){
int fmax = 1;
// cresc fluxul pe fiecare arc direct din drumul de crestere
// scad fluxul pe fiecare arc invers din drumul de crestere
int nod = t;
while(nod != s){
int prev = tati[nod];
flux[prev][nod] += fmax;
flux[nod][prev] -= fmax;
nod = prev;
}
}
void edmonds_karp(){
queue<int> coada;
vector<int> tati(202, -1);
vector<int> viz(202, 0);
while(constr_drum_crestere(coada, tati, viz)){
reviz_drum(coada, tati, viz);
coada = queue<int>();
tati = vector<int>(202, -1);
viz = vector<int>(202, 0);
}
}
int main(){
f >> n;
constr_graf();
edmonds_karp();
g << m << endl;
//parcurgem graful si vedem ce muchii
for(int nod = 1; nod <= n; nod++)
for(int copie = n; copie <= n*2; copie++)
if(flux[nod][copie])
g << nod << " " << copie - n << endl;
g.close();
return 0;
}