Pagini recente » Cod sursa (job #742175) | Cod sursa (job #1206385) | Cod sursa (job #555247) | Cod sursa (job #321483) | Cod sursa (job #2960684)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<vector<int>> graf;
vector<int> vizitat;
vector<int> tata;
vector<vector<int>> capacitate;
vector<vector<int>> flux;
int n, sursa, dest;
void bfs(){
fill(vizitat.begin(), vizitat.end(), 0);
queue<int> coada;
coada.push(sursa);
vizitat[sursa] = 1;
while(!coada.empty()){
int nod = coada.front();
coada.pop();
if(nod == dest)
continue;
for(auto &vecin:graf[nod]){
if(capacitate[nod][vecin] == flux[nod][vecin] || vizitat[vecin] == 1)
continue;
vizitat[vecin] = 1;
tata[vecin] = nod;
coada.push(vecin);
}
}
}
int fluxMaxim(){
int maxFlux = 0;
//facem bfs cat timp mai exista drumuri de la sursa la destinatie pe care sa le verificam pentru fluxul maxim
bfs();
//cout<<"dupa bfs";
while(vizitat[dest] == 1){
//daca am ajuns la destinatie, inseamna ca am gasit un nou drum si verificam fluxul maxim pe acest drum
for(auto vecin: graf[dest]){
if(capacitate[vecin][dest] == flux[vecin][dest]) //daca nu mai am capacitate pe muchia respectiva, nu o mai verific
continue;
tata[dest] = vecin;
//memoram cat mai putem sa adaugam pe acest drum
//sunt sanse ca din cauza ordinei in care am luat drumurile, unul din drumuri sa nu ajunga la capacitatea maxima, fiind
//blocat de un alt drum
int minim = capacitate[tata[dest]][dest] - flux[tata[dest]][dest];
vecin = tata[dest];
while(vecin != sursa){
minim = min(capacitate[tata[vecin]][vecin] - flux[tata[vecin]][vecin], minim);
vecin = tata[vecin];
}
//la final avem in minim cat mai putem sa adaugam pe acest drum
vecin = dest;
while(vecin != sursa){
//adaugam
flux[tata[vecin]][vecin] += minim;
flux[vecin][tata[vecin]] -= minim;
vecin = tata[vecin];
}
maxFlux += minim;
}
bfs();
//cout<<"dupa alt bfs\n";
//cout<<maxFlux;
//cout<<"\n";
}
return maxFlux;
}
int main() {
f>>n;
sursa = 0;
dest = 2 * n + 1;
int nr_noduri_graf = 2 * n + 2;
graf.resize(nr_noduri_graf);
vizitat.resize(nr_noduri_graf);
tata.resize(nr_noduri_graf); //tata[i] = nodul din care am ajuns in nodul i
capacitate.resize(nr_noduri_graf, vector<int>(nr_noduri_graf, 0)); //capacitatea de pe muchia (i, j)
flux.resize(nr_noduri_graf, vector<int>(nr_noduri_graf, 0)); //fluxul de pe muchia (i, j)
for(int i = 1; i <= n; i++){
int grad_in, grad_out; //grad_in = numarul de muchii care intra in nodul i, grad_out = numarul de muchii care ies din nodul i
f>>grad_out>>grad_in;
capacitate[sursa][i] = grad_out;
capacitate[i + n][dest] = grad_in;
graf[sursa].push_back(i);
graf[i + n].push_back(dest);
graf[i].push_back(sursa);
graf[dest].push_back(i + n);
for(int j = 1; j <= n; j++){
if(i!=j)
{
capacitate[i][j + n] = 1;
graf[i].push_back(j + n);
graf[j + n].push_back(i);
}
}
}
g<<fluxMaxim()<<"\n";
//nodurile cuplate sunt cele care au fluxul maxim pe muchia (i, j) = capacitatea de pe muchia (i, j)
//muchiile respective nu sunt adiacente nici cu sursa, nici cu destinatia
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(capacitate[i][j + n] == flux[i][j + n] && i != j){
g<<i<<" "<<j<<"\n";
}
}
}
return 0;
}