#ifndef AF_LABORATOR1_GRAF_H
#define AF_LABORATOR1_GRAF_H
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
#include <stack>
#include <set>
#include<cstdio>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.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<int> rezultat;//vectorul in care se va construi rezultatul functiilor recursive
vector<int> tati;//vectorul de tati folosit in parcurgeri(vector utilizat in comun de metodele bfs_maxflow si Maxflow)
vector<bool> vizitat; //vector folosita in parcurgeri pentru a retine ce noduri au fot vizitate
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<vector<int>> la; //vector cu listele de adiacenta
vector<muchie_cost> vmc; //vector de muchii cu cost
vector<vector<arc>> la_arce; //vector cu listele de adiacenta ale nodurilor dintr-un graf orientat(folosita pentru metodele Dijkstra si Bellman_Ford)
bool orientat; //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_rec(int x, vector<int> & parcurgere, vector<int> & 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 dfs_mc(int x, int parinte, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result, vector<bool> & vizitat);//subprogram de tip dfs folosit de metoda Muchii_critice
void dfs_bcx(int x, int parinte, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe, vector<bool> & vizitat); //subprogram de tip dfs folosit de metoda Biconexe
void dfs_ctc(int x, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe, vector<bool> & vizitat);//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)
int calc(int nod_start, int masca, int nod_dest);//metoda folosita de metoda Hamilton pentru a calcula costul lantului de la nodul de start
//la nodul destinatie, drum ce trece doar prin noduri ce au bitul corespunzator din scrierea binara a mastii cu valoarea 1
public:
Graf(int n, int m, bool orientat, 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
vector<int> dfs(int x);//dfs=parcurgere dfs a grafului
vector<int> bfs(int x);//bfs = parcurgere bfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
vector<int> SortareTop(); //sortarea topologica a grafului(daca acesta este orientat si aciclic); afiseaza vectorul sortarii
vector<set<int>> Biconexe(); //metoda ce afiseaza vectorul de componente biconexe(care sunt vectori de noduri) ale grafului
vector<vector<int>> Muchii_critice(); //metoda ce afiseaza vectorul de muchii critice(care sunt vectori cu 2 elemente) ale grafului
vector<set<int>> Componente_Tare_Conexe(); //metoda ce afiseaza vectorul de componente tareconexe
vector<pair<int,int>> Kruskal(int &cost_total);//metoda ce implementeaza algoritmul lui Kruskal de determinare a APM-ului
vector<int> Dijkstra(int s); //metoda ce implementeaza algoritmul lui Dijkstra de determinare a drumurilor minime de la un nod dat
// la toate celelalte, folosind un heap (complexitate O(m*logn))
vector<int> BellmanFord(int s); //metoda ce implementeaza algoritmul Bellman-Ford de determinare a drumurilor minime de la un nod dat 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)
int Darb();//metoda ce returneaza diametrul arborelui(disanta dintre cele mai indepartate doua frunze ale arborelui) - complexitate O(n)
vector<int> Ciclueuler(); //metoda ce returneaza un ciclu eulerian din graf, daca acesta exista sau -1 altfel - complexitate O(m)
int Hamilton(vector<vector<int>> &M); //metoda ce returneaza costul minim al unui ciclu hamiltonian daca graful dat are un astfel de ciclu
//metoda primeste ca parametru o matrice goala utilizata la memoizare
};
#endif //AF_LABORATOR1_GRAF_H
//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 orientat, bool costuri)
{
this->n = n;
this->m = m;
this->orientat = orientat;
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(!orientat)
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_rec(int x, vector<int> & parcurgere, vector<int> & vizitat)
{
vizitat[x] = true;
//std::cout << x << " ";
parcurgere.push_back(x);
for(int i=0; i<la[x].size(); ++i)
{
int y = la[x][i];
if (vizitat[y] == false)
{
dfs_rec(y, parcurgere, vizitat);
tati[y]=x;
}
}
}
vector<int> Graf::dfs(int x)
{
vector<int> parcurgere;
tati.clear();
tati.resize(n+1);
vector<int> vizitat(n+1, 0);
dfs_rec(x, parcurgere, vizitat);
return parcurgere;
}
vector<int> Graf::bfs(int x)
{
vizitat.clear();
tati.clear();
rezultat.clear();
vizitat.resize(n+1);
tati.resize(n+1);
queue<int> q;
q.push(x);
vizitat[x]=1;
while(!q.empty())
{
x = q.front();
//std::cout << x << " ";
rezultat.push_back(x);
q.pop();
for(int i=0; i<la[x].size(); ++i)
{
int y=la[x][i];
if(!vizitat[y])
{
q.push(y);
tati[y]=x;
vizitat[y]=true;
}
}
}
return rezultat;
}
vector<int> Graf::SortareTop()
{
if(orientat == false)
{ cout << "Metoda SortareTop este folosita doar la grafurile orientate aciclice!\n";
return {};
}
//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
vector<int> rez;
rez.reserve(n+1);
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);
}
rez.push_back(x);
//cout << x << " ";
}
return rez;
}
void Graf::dfs_bcx(int x, int parinte, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe, vector<bool> & vizitat)
{
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, moment, low, stiva, timp, biconexe, vizitat);
//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];
}
}
}
}
vector<set<int>> Graf::Biconexe()
{
vector<set<int>> biconexe; //vectorul de componente biconexe
if(orientat == true)
{ cout << "Metoda Biconexe este folosita doar la grafurile neorientate!\n";
return biconexe;
}
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
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,moment,low,stiva, timp, biconexe, vizitat);
// 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";
// }
return biconexe;
}
void Graf::dfs_mc(int x, int parinte, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result, vector<bool> & vizitat)
{
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, moment, low, timp, result, vizitat);
//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({x,z});
}
else //muchie de intoarcere
{
if(z!=parinte && low[x] > moment[z])
{
low[x] = moment[z];
}
}
}
}
vector<vector<int>> Graf::Muchii_critice()
{
vector<vector<int>> result; //vectorul de componente biconexe
if(orientat == true)
{ cout << "Metoda Muchii_critice este folosita doar la grafurile neorientate!\n";
return result;
}
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
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,moment,low, timp, result, vizitat);
// 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";
// }
return result;
}
void Graf::dfs_ctc(int x, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe, vector<bool> & vizitat)
{
vizitat[x] = true;
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] == false)
{
dfs_ctc(z, moment, low, stiva, in_stack, timp, tareconexe, vizitat);
//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);
}
}
vector<set<int>> Graf::Componente_Tare_Conexe()
{
vector<set<int>> tareconexe; //vectorul de componente tare-conexe
if(orientat == false)
{ cout << "Metoda Componente_Tare_Conexe este folosita doar la grafurile orientate!\n";
return tareconexe;
}
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
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, moment, low, stiva, in_stack, timp, tareconexe, vizitat);
// 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";
// }
return tareconexe;
}
vector<pair<int,int>> Graf::Kruskal(int &cost_total)
{
if(orientat == 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
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);
}
vector<pair<int,int>> rez(contor+1);
//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)
{
rez[i].first = rezultat[i].x;
rez[i].second = rezultat[i].y;
}
return rez;
}
vector<int> Graf::Dijkstra(int s)
{
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[s] = 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[s].size(); ++i)
{
H.push(la_arce[s][i]);
d[la_arce[s][i].y] = la_arce[s][i].distanta;
t[la_arce[s][i].y] = s;
}
//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 " << s << " 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";
for(int i=2; i<=n; ++i)
if(d[i] == 1000000001)
d[i]=0;
return d;
}
vector<int> Graf::BellmanFord(int s)
{
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[s] = 0;
selectat[s] = 1;
cnt[s] = 1;
queue<int> q; //coada in care se vor pune nodurile ale caror disante s-au modificat(pentru optimizarea algoritmului)
q.push(s);
//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 " << s << " 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] << " ";
// }
if(circuit_negativ)
return {};
else
{
for(int i=2; i<=n; ++i)
if(d[i] == 1000000001)
d[i] = 0;
}
return d;
}
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)
{
tati[D] = 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;
//punem in coada nodul de start
q.push(S);
tati[S] = 0;
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[x].size(); ++i)
{
int y = la[x][i];
//daca nodul adiacent curent nu a fost vizitat si arcul de la x la y este unul nesaturat
if(vizitat[y] == true || capacitate[x][y] == flux[x][y])
continue;
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
//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);
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;
la[i].push_back(y);
la[y].push_back(i);
}
//cat timp gasesc un drum de ameliorare de la sursa la destinatie
while(bfs_maxflow(S, D))
{
for(int i=0; i<la[D].size(); ++i)
{
int y = la[D][i];
if (flux[y][D] == capacitate[y][D] || !vizitat[y])
continue;
tati[D] = y;
int a = (1<<30);
//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 Graf::Darb()
{
//doar la arbori(graf neorientat conex si aciclic)
vector<int> parcurgere = bfs(1);
parcurgere = bfs(parcurgere[n-1]);
int diametru=0;
int i = parcurgere[n-1];
do
{
diametru+=1;
i = tati[i];
}while(i!=0);
return diametru;
}
vector<int> Graf::Ciclueuler()
{
//verificam daca toate nodurile au grade pare(daca nu returnam -1)
for(int i=1; i<=n; ++i)
{
if(la_arce[i].size()%2 != 0)
return {-1};
}
vector<int> rezultat;
vector<bool> mv;
mv.resize(m+1, 0);//vector ce retine pt fiecare muchie daca a fost sau nu vizitata
//declaram stiva si punem in ea primul nod vizitat
stack<int> s;
s.push(1);
//cat timp stiva nu e goala(mai avem elemente de procesat)
while(!s.empty())
{
//extragem nod din stiva
int nod = s.top();
//daca acesta mai are vecini
if(!la_arce[nod].empty())
{
//extragem un vecin
int y = la_arce[nod].back().y;
int poz = la_arce[nod].back().distanta;
la_arce[nod].pop_back();
//stergem muchia dintre nodul curent si vecinul sau(din ambele liste de adiacenta)
if(!mv[poz])
{
mv[poz] = true;
s.push(y);
}
}
else
{
s.pop();
rezultat.push_back(nod);
}
}
//scoatem ultimul nod deoarece apare si la inceputul lantului
rezultat.pop_back();
return rezultat;
}
vector<vector<int>> M; // matrice folosita la memoizare ce va avea dimensiunile 2^n si n
int Graf::calc(int nod_start, int masca, int nod_dest)
{
//daca in matricea de memoizare avem -1,
//inseamna ca pana la acel punct nu s-a calculat valoarea
//si o vom calcula pe baza valorilor din urma
if(M[masca][nod_dest] == -1)
{
M[masca][nod_dest] = (1<<30); //initializam cu infinit
for(int i=0; i<la[nod_dest].size(); ++i)
if(masca & (1<<la[nod_dest][i])!=0) //daca pe pozitia aferenta nodului adiacent curent se gasete 1 in masca
{
//daca am ajuns din nou la start si nod_start este diferit de nod_dest
if( la[nod_dest][i] == nod_start && ((masca xor (1<<nod_dest)) != (1<<nod_start)) )
continue; //pentru ca a fost deja calculat
M[masca][nod_dest] = min( M[masca][nod_dest], calc(nod_start, (masca xor (1<<nod_dest)), la[nod_dest][i]) + capacitate[la[nod_dest][i]][nod_dest] );
}
}
return M[masca][nod_dest];
}
int Graf::Hamilton(vector<vector<int>> &M)
{
int cost = (1<<30);//variabila in care se va salva costul minim al lantului hamiltonian, initial egala cu infinit
//vom folosi matricea capacitate deja existenta in clasa graf pentru a retine costurile arcelor
//dimensionam matricea de costuri si o umplem cu valoarea infinit
capacitate.clear();
capacitate.resize(n+1, vector<int>(n+1, (1<<30)));
//completam matricea de costuri(costurile sunt luate din listel de adiacenta)
for(int i=0; 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;
la[y].push_back(i);
}
for(int i=0; i<n; ++i)
{
//la fiecare nod reinitializam matricea folosita la memoizare(folosita la calculul costului minim al unui drum de la
// nodul i la fiecare din nodurile spre care are drum)
M.clear();
M.resize((1<<n), vector<int>(n, -1));
//initializam lantul format doar din nodul i (nodul curent) cu 0
M[(1<<i)][i] = 0;
//pentru fiecare nod adiacent lui i(noduri in care se ajunge plecand din i)
//actualizam costul minim(variabila cost)
//costul va fi minimul dintre valoarea sa actuala si costul arcului de la nodul adiacent la i
//la care adunam costul unui drumu
//de la i la adiacent
//(1<<n)-1 masca ce are toti bitii setati la 1
for(int v=0; v<la[i].size(); ++v)
cost = min(cost, calc(i,(1<<n)-1,la[i][v]) + capacitate[la[i][v]][i]);
}
return cost;
}
int main()
{
int n,m;
fin >> n >> m;
Graf g(n, m, 1, 1);
for(int i=1; i<=m; ++i)
{
int x, y, c;
fin >> x >> y >> c;
g.Add_arc(x, y, c);
}
fout << g.Hamilton(M);
return 0;
}
Ioan Ionescu ionut31