#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
#include <stack>
#include <set>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
//strucutra unui arc cu distanta(cost) din graf(folosita in metodele Dijkstra si Bellman_Ford si de clasa Min_heap)
struct arc
{
int y, distanta;
arc(int b, int d)
{
y = b;
distanta = d;
}
arc(){}
bool operator < (const arc &a) const //operator pentru compararea distantelor(costurilor) a doua arce
{return distanta < a.distanta;}
};
class Graf
{
private:
//strucutra unei muchii din graf(folosita in medota Biconexe)
struct muchie
{
int x,y;
muchie(int a, int b)
{
x=a;
y=b;
}
muchie(){}
};
//strucutra unei muchii cu cost din graf(folosita in medota Kruskal)
struct muchie_cost
{
int x,y,cost;
muchie_cost(int a, int b, int c)
{
x=a;
y=b;
cost=c;
}
muchie_cost(){}
bool operator < (const muchie_cost &m) const //operator pentru compararea costurilor a doua muchii
{return cost < m.cost;}
};
int n; //nr de noduri
int m; //nr de muchii
vector<vector<int> > flux; //matrice in care se moreaza fluxurile dintre doua noduri adiacente din graf(utilizat in comun de metodele bfs_maxflow si Maxflow)
vector<vector<int> > capacitate; //matrice in care se moreaza capacitatile dintre doua noduri adiacente din graf(utilizat in comun de metodele bfs_maxflow si Maxflow)
vector<int> traseu;//vector utilizat in comun de metodele bfs_maxflow si Maxflow si retine, pentru fiecare arc nesaturat
// de la x la y, traseu[y] = x, iar pentru fiecare arc de la y la x retine traseu[y] = -x;
//tine loc si de vector de tati si de vector de vizitat
vector<vector<int> > la; //vector cu listele de adiacenta
vector<muchie_cost> vmc; //vector de muchii cu cost
vector<int> tati;
vector<int> vizitat;
vector<vector<arc> > la_arce; //vector cu listele de adiacenta ale nodurilor dintr-un graf orientat(folosita pentru metodele Dijkstra si Bellman_Ford)
bool tip; //variabila care ne spune daca graful este orientat sau nu(daca este orientat este true altfel este false)
bool costuri;//variabila care ne spune daca muchiile grafului au sau nu asociate costuri(daca da costuri este true altfel este false)
void dfs_mc(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int> > &result);//subprogram de tip dfs folosit de metoda Muchii_critice
void dfs_bcx(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int> > &biconexe); //subprogram de tip dfs folosit de metoda Biconexe
void dfs_ctc(int x, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int> > &tareconexe);//subprogram de tip dfs folosit de metoda Componente_Tare_Conexe
bool bfs_maxflow(int S, int D);//metoda ce implementeaza o parcurgere bfs si intoarce false daca din sursa nu se poate ajunge in destinatie, folosita in algoritmul Edmonds-Karp;
//complexitate O(n)
public:
Graf(int n, int m, bool tip, bool costuri);//constructor parametrizat care primeste si tipul grafului si daca muchiile au sau nu costuri: orientat(tip==true) sau neorientat(tip==false) si cu costuri pe muchii(costuri==true) sau fara(costuri==false)
void Add_edge(int x, int y); //metoda de adaugare a unei muchii in graf
void Add_edge_c(int x, int y, int c); //metoda de adaugare a unei muchii cu cost in graf
void Add_arc(int x, int y, int d); //metoda de adaugare a unui arc cu distanta in graf
void dfs(int x, vector<bool> &vizitat); //dfs = parcurgere dfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
void bfs(int x, vector<bool> &vizitat);//bfs = parcurgere bfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
void SortareTop(); //sortarea topologica a grafului(daca acesta este orientat si aciclic); afiseaza vectorul sortarii
void Biconexe(); //metoda ce afiseaza vectorul de componente biconexe(care sunt vectori de noduri) ale grafului
void Muchii_critice(); //metoda ce afiseaza vectorul de muchii critice(care sunt vectori cu 2 elemente) ale grafului
void Componente_Tare_Conexe(); //metoda ce afiseaza vectorul de componente tareconexe
void Kruskal();//metoda ce implementeaza algoritmul lui Kruskal de determinare a APM-ului
void Dijkstra(); //metoda ce implementeaza algoritmul lui Dijkstra de determinare a drumurilor minime de la un nod
// la toate celelalte, folosind un heap (complexitate O(m*logn))
void BellmanFord(); //metoda ce implementeaza algoritmul Bellman-Ford de determinare a drumurilor minime de la un nod la toate celelalte,
//depistand ciclurile de cost negativ; algoritmul floseste o coada (complexitate O(m*n))
int Maxflow(int S, int D);//metoda ce implementeaza algoritmul Edmonds-Karp de determinarea a fluxului maxim ce poate fi trimis printr-o
//retea(graf orientat alea carui muchii au asociate capacitati); complexitate O(n*(m^2))
vector<vector<int> > RoyFloyd();//metoda ce implementeaza algoritmul Roy-Floyd de determinare a matricei de drumuri minime dintr-un graf;
//complexitate O(n^3)
};
//clasa de multimi disjuncte folosita la algoritmul lui Kruskal
class DisjointSets
{
private:
int n; //numarul de noduri
vector<int> rep; //vectorul de reprezentanti(conform cursului)
vector<int> h; //vector ce va retine inaltimile arborilor
public:
DisjointSets(int n);//constructor parametrizat care face si initializarea vectorului de preprezentanti
int Reprezentant(int x);//metoda ce returneaza reprezentantul unui nod x dat
void Reuniune(int x, int y);//metoda ce reuneste arborii care contin nodurile x si y
};
DisjointSets::DisjointSets(int n)
{
this->n = n;
//initializam vectorul de reprezentanti si pe cel de inaltimi
rep.resize(n+1);
h.resize(n+1);
for(int i=1; i<=n; ++i)
rep[i] = i;
};
int DisjointSets::Reprezentant(int x)
{
//daca x este chiar radacina(adica daca el este reprezentantul sau) il returnez
if(x == rep[x])
return x;
else //altfel reprezentantul lui x va fi reprezentantul tatalui sau(apel recursiv)
{
//efectuam compresia asupra arborelui
int r = Reprezentant(rep[x]); //aflu reprezentantul parintelui lui x
rep[x] = r;
//returnam reprezentantul lui x
return r;
}
}
void DisjointSets::Reuniune(int x, int y)
{
//aflam rep lui x si y
int rx = Reprezentant(x);
int ry = Reprezentant(y);
//daca x si y au acelasi reprezentant, atunci acestia sunt deja in aceeasi multime(nu am ce sa reunesc)
if(rx == ry)
return;
//subordonez reprezentantul din arborele cu inaltime mai mica reprezentantului din arborele cu inaltime mai mare
if(h[rx] < h[ry])
rep[rx] = ry;
else if(h[rx] > h[ry])
rep[ry] = rx;
else //au inaltimi egale caz in care inaltimea creste cu 1 dupa subordonare
{
rep[rx] = ry;
h[ry]++;
}
}
//clasa Min_heap folosita la pastrarea in ordinea crescatoare a distantelor(costurilor) arcelor din graf (folosita in metoda Dijsktra)
class Min_heap
{
private:
int n; //nr de noduri din heap
int N; //numarul de noduri distincte din heap
vector<arc> h; //vector de arce prin care este reprezentat heap-ul
vector<int> pozitii; //vector ce retine pe ce pozitie in heap se afla fiecare nod x
public:
Min_heap(int n); //constructor parametrizat pt heap
arc pop(); //metoda care scoate minimul din heap(varful)
void push(arc a); //metoda care insereaza in heap un arc
void go_down(int i, int n); //metoda de deplasare in jos in heap(folosita cand se extrage sau se insereaza cate un arc, pt a mentine prop de min-heap)
void go_up(int i); //metoda de deplasare in sus in heap(folosita cand se extrage sau se insereaza cate un arc, pt a mentine prop de min-heap)
int poz_min(int i, int n); //metoda care obtine pozitia fiului minim al unui nod abia inserta in heap
bool empty(); //metoda care testeaza daca heap-ul este gol
};
bool Min_heap::empty()
{
if(N==0)
return true;
else
return false;
}
Min_heap::Min_heap(int n)
{
h.resize(n+1);
pozitii.resize(n+1);
N = 0;
}
int Min_heap::poz_min(int i, int n)
{
if(2*i>n) //daca nodul este frunza
return 0;
if(2*i + 1 <= n) //daca nodul nu este frunza si exista ambii descendent
{
if(h[2*i].distanta <= h[2*i+1].distanta)
return 2*i;
else
return 2*i+1;
}
else //nodul nu este frunza dar am doar descendent stang
return 2*i;
}
void Min_heap::go_up(int i)
{
if(i>1) //daca nodul nu este deja in varf
{
int p = i/2; //aflu parintele
if(h[i] < h[p])
{
pozitii[h[i].y] = p;
pozitii[h[p].y] = i;
arc aux = h[p];
h[p] = h[i];
h[i] = aux;
go_up(p);
}
}
}
void Min_heap::go_down(int i, int n)
{
if(i<=n/2) //daca nodul nu este deja frunz
{
int m = poz_min(i,n); //aflu pozitia celui mai mic dintre fii
if(h[m] < h[i])
{
pozitii[h[i].y] = m;
pozitii[h[m].y] = i;
arc aux = h[m];
h[m] = h[i];
h[i] = aux;
go_down(m, n);
}
}
}
arc Min_heap::pop()
{
pozitii[h[N].y] = 1;
pozitii[h[1].y] = 0;
arc aux = h[1];
h[1] = h[N];
h[N] = aux;
N--;
go_down(1, N);
return h[N+1];
}
void Min_heap::push(arc a)
{
//daca nodul y deja exista in heap il elimin, pentru a ne asigura ca un nod nu apare de mai multe ori in heap
if(pozitii[a.y]>0)
{
arc aux = h[pozitii[a.y]];
pozitii[h[N].y] = pozitii[a.y];
h[pozitii[a.y]] = h[N];
h[N] = aux;
N--;
go_down(pozitii[a.y], N);
}
//adaug noul nod in heap si memorez pozitia sa
N++;
h[N] = a;
pozitii[a.y] = N;
go_up(N);
}
Graf::Graf(int n, int m, bool tip, bool costuri)
{
this->n = n;
this->m = m;
this->tip = tip;
this->costuri = costuri;
la.resize(n+1);
la_arce.resize(n+1);
}
void Graf::Add_edge(int x, int y)
{
la[x].push_back(y);
if(!tip)
la[y].push_back(x);
}
void Graf::Add_edge_c(int x, int y, int c)
{
vmc.push_back(muchie_cost(x,y,c));
}
void Graf::Add_arc(int x, int y, int d)
{
la_arce[x].push_back(arc(y,d));
}
void Graf::dfs(int x, vector<bool> &vizitat)
{
assert(vizitat.size()>=n);//verific daca vetorul dat ca parametru are dimensiunea corespunzatoare
vizitat[x] = true;
std::cout << x << " ";
for(int i=0; i<la[x].size(); ++i)
{
int y = la[x][i];
if (vizitat[y] == false)
dfs(y, vizitat);
}
}
void Graf::bfs(int x, vector<bool> &vizitat)
{
assert(vizitat.size()>=n);//verific daca vetorul dat ca parametru are dimensiunea corespunzatoare
queue<int> q;
q.push(x);
vizitat[x]=1;
while(!q.empty())
{
x = q.front();
std::cout << x << " ";
q.pop();
for(int i=0; i<la[x].size(); ++i)
{
int y=la[x][i];
if(!vizitat[y])
{
q.push(y);
vizitat[y]=true;
}
}
}
}
void Graf::SortareTop()
{
if(tip == false)
{ cout << "Metoda SortareTop este folosita doar la grafurile orientate aciclice!\n";
return;
}
cout<< "Sortarea topologica a grafului dat este: ";
//completam vector in care retinem gradele interioare ale nodurilor
vector<int> gr_int(n+1);
for(int i=1; i<=n; ++i)
{
for(int j=0; j<la[i].size(); ++j)
++gr_int[la[i][j]];
}
queue<int> q; //coada folosita la sortarea topologica
//parcurgem vectorul de grade si punem in coada nodurile cu gradul interior 0
for(int i=1; i<=n; ++i)
if(gr_int[i]==0)
q.push(i);
//parcurgem coada pentru a obtine o sortare topologica
while(!q.empty())
{
int x;
//extragem un nod din coada
x = q.front();
q.pop();
//scadeam gradele interioare ale nodurilor in care intra nodul curent
for(int i=0; i<la[x].size(); ++i)
{
int y = la[x][i];
--gr_int[y];
if(gr_int[y] == 0)
q.push(y);
}
cout << x << " ";
}
cout << "\n(In cazul in care graful prezinta cicluri sortarea afisata este doar sortarea topologica a nodurilor ce nu fac parte din vreun ciclu)";
}
void Graf::dfs_bcx(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int> > &biconexe)
{
vizitat[x] = 1;
moment[x] = timp++;
low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)
//parcurg lista de adiacente a lui x
for(int i=0; i<la[x].size(); ++i)
{
int z = la[x][i];
if (vizitat[z] == 0)
{
stiva.push(muchie(x,z));//adaug muchia in stiva de muchii
dfs_bcx(z, x, vizitat, moment, low, stiva, timp, biconexe);
//daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
// (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
if(low[x] > low[z])
low[x] = low[z];
//determinare componente biconexe
if(moment[x] <= low[z]) //deci x este punct critic
{
set<int> componenta;
int a, b; //capetele unei muchii
do
{
muchie m=stiva.top();
stiva.pop();
a=m.x;
b=m.y;
componenta.insert(a);
componenta.insert(b);
}while(a!=x || b!=z);
biconexe.push_back(componenta);//adaug componenta in vectorul de componente biconexe
}
}
else //am dat de o muchie de intoarcere
{
if(z!=parinte) //verific ca z sa nu fie parinte al lui x
{ //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
// strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
// (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
if (low[x] > moment[z])
low[x] = moment[z];
}
}
}
}
void Graf::Biconexe()
{
if(tip == true)
{ cout << "Metoda Biconexe este folosita doar la grafurile neorientate!\n";
return;
}
vector<bool> vizitat(n+1); //vector vizitat
vector<int> moment(n+1); //vector ce retine momentul in care se viziteaza prima oara un nod di graf
vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
stack<muchie> stiva; //stiva in care vom retine muchiile unei componente biconeexe
vector<set<int> > biconexe; //vectorul de componente biconexe
int timp = 0;// timp = contor de timp pentru crearea vectorului moment
//daca graful nu este conex, se analizeaza fiecare componenta conexa
for(int i=1; i<=n; ++i)
if(!vizitat[i])
dfs_bcx(i,0,vizitat,moment,low,stiva, timp, biconexe);
cout << "Numarul de componente biconexe: " << biconexe.size() << "\n";
cout<< "Componentele biconexe sunt: \n";
for(int i=0; i<biconexe.size(); ++i)
{
cout << i+1 << ") ";
for(set<int>::iterator it=biconexe[i].begin(); it!=biconexe[i].end(); ++it)
cout << *it << " ";
cout << "\n";
}
}
void Graf::dfs_mc(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int> > &result)
{
vizitat[x] = 1;
moment[x] = timp++;
low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)
//parcurg lista de adiacente a lui x
for(int i=0; i<la[x].size(); ++i)
{
int z = la[x][i];
if (vizitat[z] == 0)
{
dfs_mc(z, x, vizitat, moment, low, timp, result);
//daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
// (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
if(low[x] > low[z])
low[x] = low[z];
//daca este muchie critica o adaugam in result
/*
if(low[z] > moment[x])
result.push_back(make_pair(x,z));
*/
}
else //muchie de intoarcere
{
if(z!=parinte && low[x] > moment[z])
{
low[x] = moment[z];
}
}
}
}
void Graf::Muchii_critice()
{
if(tip == true)
{ cout << "Metoda Muchii_critice este folosita doar la grafurile neorientate!\n";
return;
}
vector<bool> vizitat(n+1); //vector vizitat
vector<int> moment(n+1); //vector ce retine momentul in care se viziteaza prima oara un nod di graf
vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
vector<vector<int> > result; //vectorul de componente biconexe
int timp = 0;// timp = contor de timp pentru crearea vectorului moment
//daca graful nu este conex, se analizeaza fiecare componenta conexa
for(int i=1; i<=n; ++i)
if(!vizitat[i])
dfs_mc(i,0,vizitat,moment,low, timp, result);
cout << "Numarul de muchii critice: " << result.size() << "\n";
cout << "Muchiile critice sunt: \n";
for(int i=0; i<result.size(); ++i)
{
cout << i+1 << ") " << result[i][0] << " " << result[i][1] <<"\n";
}
}
void Graf::dfs_ctc(int x, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int> > &tareconexe)
{
vizitat[x] = 1;
moment[x] = timp++;
low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)
stiva.push(x);//adaug nodul in stiva de noduri si in multimea care tine evidenta nodurilor din stiva
in_stack.insert(x);
//parcurg lista de adiacente a lui x
for(int i=0; i<la[x].size(); ++i)
{
int z = la[x][i];
if (vizitat[z] == 0)
{
dfs_ctc(z, vizitat, moment, low, stiva, in_stack, timp, tareconexe);
//daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
// (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
if(low[x] > low[z])
low[x] = low[z];
}
else if(in_stack.find(z)!=in_stack.end())//am dat de o muchie de intoarcere si nodul z face parte din noua componenta tare_conexa
{
//daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
// strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
// (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
if (low[x] > moment[z])
low[x] = moment[z];
}
}
if(low[x]==moment[x]) //daca nodul e radacina in componenta tare_conexa curenta(am avut un circuit)
{
set<int> componenta;
int y;
do{
y=stiva.top();
stiva.pop();
in_stack.erase(y);
componenta.insert(y);
}while(y!=x);
tareconexe.push_back(componenta);
}
}
void Graf::Componente_Tare_Conexe()
{
if(tip == false)
{ cout << "Metoda Componente_Tare_Conexe este folosita doar la grafurile orientate!\n";
return;
}
vector<bool> vizitat(n+1);
vector<int> moment(n+1); //vector ce retine momentul in care se viziteaza prima oara un nod di graf
vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
stack<int> stiva; //stiva in care vom retine nodurile unei componente tare-conexe
set<int> in_stack;//multimne care retine ce elemente sunt in stiva la un anumit moment
vector<set<int> > tareconexe; //vectorul de componente tare-conexe
int timp=0;
//daca graful nu este conex, se analizeaza fiecare componenta tare-conexa
for(int j=1; j<=n; ++j)
if(vizitat[j]==0)
dfs_ctc(j, vizitat, moment, low, stiva, in_stack, timp, tareconexe);
cout << "Numarul de componente tareconexe: "<< tareconexe.size() << "\n";
cout<< "Componentele tareconexe sunt: \n";
for(int i=0; i<tareconexe.size(); ++i)
{
cout << i+1 << ") ";
for(set<int>::iterator it=tareconexe[i].begin(); it!=tareconexe[i].end(); ++it)
cout << *it << " ";
cout << "\n";
}
}
void Graf::Kruskal()
{
if(tip == true)
{ cout << "Metoda Kruskal de determinare a APM-ului este folosita doar la grafurile neorientate conexe!\n";
return;
}
if(costuri == false)
{ cout << "Metoda Kruskal de determinare a APM-ului este folosita doar la grafurile ale caror muchii au asociate costuri!\n";
return;
}
//sortam vectorul de muchii crescator dupa cost(in M*logM)
sort(vmc.begin(), vmc.end());
//definim o padure de multimi disjuncte
DisjointSets dj(n);
vector<muchie> rezultat;//vectorul in care vom retine muchiile APM-ului
rezultat.resize(n-1);//APM-ul va avea exact n-1 muchii(pt ca este arbore)
int contor = 0;//variabila care retine cate muchii au fost selectate pana la un anumit moment de timp
int cost_total = 0;
for(int i=0; i<m; ++i)
{
//obtin extremitatiile muchiei curente
int x = vmc[i].x;
int y = vmc[i].y;
//aflu reprezentatntii lui x si y(pt a vedea daca sunt sau nu in multimi disjuncte)
int rx = dj.Reprezentant(x);
int ry = dj.Reprezentant(y);
//au acelasi reprezentant muchia nu este buna si trec mai departe
if(rx == ry)
continue;
//adaug muchia curenta in rezultat(in APM)
rezultat[contor] = muchie(x,y);
contor++;
cost_total+=vmc[i].cost;
//daca am atins numarul de muchii necesare APM-ului ne oprim
if(contor == n-1)
break;
//reunim multimiile lui x si y
dj.Reuniune(x,y);
}
//afisam rezultatul(APM-ul)
cout << "\n";
cout << "Costul total al APM-ului este: " << cost_total << "\n";
cout << "Numarul de muchii din APM este: " << n-1 << "\n";
cout << "Muchiile APM-ului sunt:\n";
for(int i=0; i<contor; ++i)
cout << rezultat[i].x << " " << rezultat[i].y << "\n";
}
void Graf::Dijkstra()
{
if(costuri == false)
{ cout << "Metoda Dijkstra de determinare a drumurilor de cost minim este folosita doar la grafurile ale caror muchii au asociate costuri(distante)!\n";
return;
}
//initializare
vector<int> d(n+1, 1000000001); //vector de distante
vector<int> t(n+1, 0); //vectorul de tati
d[1] = 0;
Min_heap H(n); //declaram heapul
//punem in heap distantele de la nodul de start la toate nodurile sale adiacente si actualizam tatal acestor noduri(care este chiar nodul de start)
//impreuna cu distantele(care sunt chiar costurile muchiilor dintre nodul 1 si noduriel respective)
for(int i=0; i<la_arce[1].size(); ++i)
{
H.push(la_arce[1][i]);
d[la_arce[1][i].y] = la_arce[1][i].distanta;
t[la_arce[1][i].y] = 1;
}
//in mod repetat, pentru restul de n-1 noduri, selectez nodurile adiacente(la fiecare pas este ales nodul cu distanta cea mai mica
//care nu a mai fost selectat)
//cele in care se poate ajunge in ele
while(!H.empty())
{
arc ac = H.pop(); //arcul curent
for(int i=0; i<la_arce[ac.y].size(); ++i)
{
int z = la_arce[ac.y][i].y; //nodul in care s-a ajuns din nodul curent
int nd = d[ac.y] + la_arce[ac.y][i].distanta;//noua distanta
if(nd < d[z]) //relaxare muchie
{
d[z] = nd;
t[z] = ac.y;
H.push(arc(z,nd));
}
}
}
cout << "Costurile drumurile minime de la nodul 1 la toate celelelate noduri, determinate in urma algoritmului Dijkstra sunt: ";
for(int i=2; i<=n; ++i)
if(d[i] == 1000000001)
cout << 0 << " ";
else
cout << d[i] << " ";
cout << "\n";
}
void Graf::BellmanFord()
{
if(costuri == false)
{ cout << "Metoda BellmanFord de determinare a drumurilor de cost minim este folosita doar la grafurile ale caror muchii au asociate costuri(distante)!\n";
return;
}
//initializare
vector<int> d(n+1, 1000000001); //vector de distante
vector<int> cnt(n+1, 0); //vector ce retine de cate ori un nod a fost introdus in coada(de cate ori s-a modificat pe parcursul
// tuturor pasilor acel nod)
vector<int> selectat(n+1, 0); //vector ce retine daca un nod a fost pus in coada sau nu(la un pas ne intereseaza doar daca unui nod
// i se modifica distanta, nu de cate ori i se modifica distanta, asa ca nu il vom pune in coada de fiecare data cand i se modifica
// distanta, ci doar o data)
vector<int> t(n+1, 0); //vectorul de tati
d[1] = 0;
selectat[1] = 1;
cnt[1] = 1;
queue<int> q; //coada in care se vor pune nodurile ale caror disante s-au modificat(pentru optimizarea algoritmului)
q.push(1);
//fiecare iteratie a while-ului reprezinta un pas nou din algoritmul Bellman-Ford(poate avea cel mult n-1 pasi)
bool circuit_negativ = false;
while(!q.empty() && !circuit_negativ)
{
int u = q.front();
selectat[u] = 0;
//daca pt nodul u a fost modificata distanta de n ori oprim executia
if(cnt[u] == n)
{
circuit_negativ = true;
break;
}
q.pop();
for (int j = 0; j < la_arce[u].size(); ++j)
{
int v = la_arce[u][j].y;
int nd = d[u] + la_arce[u][j].distanta;// noua distanta folosita la eventuala relaxare
if (nd < d[v]) //testare pentru relaxarea drumului
{
d[v] = nd;
t[v] = u;
if(selectat[v] == 0)
{
cnt[v] ++;
selectat[v] = 1;
q.push(v);
}
}
}
}
cout << "Costurile drumurile minime de la nodul 1 la toate celelelate noduri, determinate in urma algoritmului BellmanFord sunt: ";
if(circuit_negativ)
cout << "Ciclu negativ!";
else{
for(int i=2; i<=n; ++i)
if(d[i] == 1000000001)
cout << 0 << " ";
else
cout << d[i] << " ";
}
}
vector<vector<int> > Graf::RoyFloyd()
{
//doar la grafuri cu cost
int inf = (1<<20);
vector<vector<int> > md; //matricea drumurilor unui graf, folosita in algoritmul Roy-Floyd
md.resize(n+1,vector<int>(n+1,inf));
//construim matricea drumurilor din listele de adiacenta la_arce
for(int i=1; i<=n; ++i)
for(int j=0; j<la_arce[i].size(); ++j)
if(la_arce[i][j].distanta!=0)
md[i][j+1] = la_arce[i][j].distanta;
//roy-floyd
for(int k=1; k<=n; ++k)
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if(md[i][k] + md[k][j] < md[i][j])
md[i][j] = md[i][k] + md[k][j];
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if(md[i][j] == inf || i==j)
md[i][j] = 0;
return md;
}
bool Graf::bfs_maxflow(int S, int D)
{
//golesc vectorul tati la fiecare parcurgere(pentru aflarea fiecarui drum de ameliorare)
tati.clear();
//redimensionam vectorul tati si il initializam
tati.resize(n+1, 0);
//golesc vectorul vizitat la fiecare parcurgere
vizitat.clear();
//redimensionam vectorul vizitat si il initializam
vizitat.resize(n+1, 0);
//coada folosita in parcurgerea bfs
queue<int> q;
q.push(S);
tati[S] = S;
vizitat[S] = true;
//cat timp coada nu este goala(mai am elemente de procesat) si nu s-a ajunj inca in destinatie
//parcurg bfs
while(!q.empty() && tati[D] == 0)
{
//luam urmatorul element din coada
int x = q.front();
q.pop();
//ii parcurgem lista de adiacenta
for(int i=0; i<la_arce[x].size(); ++i)
{
int y = la_arce[x][i].y;
//daca nodul adiacent curent nu a fost vizitat si arcul de la x la y este unul nesaturat
if(vizitat[y] == false && capacitate[x][y] != flux[x][y])
{
tati[y] = x;
vizitat[y] = true;
q.push(y);
}
}
}
if(tati[D]!=0)
return true;
else
return false;
}
int Graf::Maxflow(int S, int D)
{
//doar la grafuri orientate cu cost
int rez = 0;
//dimensionam si initializam matricele flux si capacitate
flux.resize(n+1, vector<int>(n+1, 0));
capacitate.resize(n+1, vector<int>(n+1, 0));
//completam matricea de capacitati(capacitatile sunt luate din listel de adiacenta)
for(int i=1; i<=n; ++i)
for(int j=0; j<la_arce[i].size(); ++j)
{
int y = la_arce[i][j].y;
capacitate[i][y] = la_arce[i][j].distanta;
}
//cat timp gasesc un drum de ameliorare de la sursa la destinatie
while(bfs_maxflow(S, D))
{
int a = INT_MAX;
//parcurg drumul de la D la S pentru a determina cu cat se poate modifica fluxul pe acel drum
for(int i=D; i!=S; i=tati[i])
a = min(a, capacitate[tati[i]][i] - flux[tati[i]][i]);
if(a == 0)
continue;
//parcurg din nou drumul pentru a face actualizarea
for(int i=D; i!=S; i=tati[i])
{
flux[tati[i]][i] += a;
flux[i][tati[i]] -= a;
}
rez +=a;
}
return rez;
}
int main()
{
int n, m, x, y, z;
fin >> n >> m;
Graf g(n,m,1,1);
for(int i=1; i<=m; ++i)
{
fin >> x >> y >> z;
g.Add_arc(x, y, z);
g.Add_arc(y, x, 0);
}
fout << g.Maxflow(1,n);
return 0;
}
elev gigel worstbyte