#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
template<int NMAX = 100009, bool listeAdiacenta = true>
class Graf
{
private:
const unsigned N, M;
vector<vector<int>> Adiacenta; // liste de adiacenta
public:
Graf(int, int);
void AdMuchieLstAdiac(int, int);
// BF-DF si aplicatii
void Bfs(int, int*);
int Dfs();
void Biconex(vector<vector<int>>&);
void CompTareConexe(vector<int>*, vector<vector<int>>&, int&);
void MuchieCritica(vector<vector<int>>&);
void ProbGraf_NoduriComune(int, int, vector<int>&);
void SortTopo(int*);
static bool HavelHakimi(int*, int);
// Drumuri minime si APM
void APM(vector<vector<int>>&, int&, vector<pair<int, int>>&);
void Dijkstra(vector<vector<pair<int, int>>>&, int, int, vector<int>&);
bool BellmanFord(vector<vector<pair<int, int>>>& Adiacenta, int, int, vector<int>&);
static void Disjoint(int, vector<vector<int>>&, vector<string>&);
// Laborator 5
void RoyFloyd(vector<vector<int>>& , int);
int DiametruArbore();
int FluxMaxim(int, int, vector<vector<int>>&);
// Laborator 6
bool CicluEulerian(int, vector<vector<pair<int, int>>>&, vector<int>&);
int CicluHamiltonian(int, vector<vector<unsigned>>&, int);
int CuplajMaxim(vector<pair<int, int>>&);
private:
void Dfs_fHelper(int, bool*);
void Biconex_fHelper(int, int, pair<int, int>*, int&, int*, int*, vector<vector<int>>&);
void CompTareConexe_Dfs(int, bool*, int*, int&);
void CompTareConexe_t_Dfs(int, bool*, vector<int>*, vector<vector<int>>&, int);
void MuchieCritica_fHelper(int, int, int*, int*, vector<vector<int>>&);
void NoduriComune_BfsInainte(int, int, int*);
void NoduriComune_BfsInapoi(int, int, int*, int*, vector<int>&);
bool FluxMaxim_Drum(int, int, vector<vector<int>>&, vector<vector<int>>&, bool*, int*);
bool Cupleaza(int, int*, int*, bool*);
static int Disjoint_CautaRadacina(int, int*);
static void Disjoint_CompresieDrumuri(int, int, int*);
static void Disjoint_Reuneste(int, int, int*, int*);
};
template<int NMAX, bool listeAdiacenta>
Graf<NMAX, listeAdiacenta>::Graf(int n, int m)
: N(n), M(m)
{
if (listeAdiacenta)
this->Adiacenta.resize(N + 1);
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::AdMuchieLstAdiac(int ini, int fin)
{
Adiacenta[ini].push_back(fin);
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::Bfs(int S, int* nrArce)
{
int coada[NMAX], st = 0, dr = 0;
for (unsigned i = 1; i <= N; ++i)
nrArce[i] = -1;
nrArce[S] = 0;
coada[st] = S;
while (st <= dr)
{
int curent = coada[st++];
for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
if(nrArce[*it] == -1)
{
coada[++dr] = *it;
nrArce[*it] = nrArce[curent] + 1;
}
}
}
template<int NMAX, bool listeAdiacenta>
int Graf<NMAX, listeAdiacenta>::Dfs()
{
bool vizitat[NMAX];
int nrComp = 0;
memset(vizitat, 0, NMAX * sizeof(bool));
for (unsigned i = 1; i <= N; ++i)
if (!vizitat[i])
{
++nrComp;
Dfs_fHelper(i, vizitat);
}
return nrComp;
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::Dfs_fHelper(int curent, bool* vizitat)
{
vizitat[curent] = true;
for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
if (!vizitat[*it])
Dfs_fHelper(*it, vizitat);
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::Biconex(vector<vector<int>>& compBic)
{
pair<int, int> Stiva[NMAX * 2];
int stVf = 0;
int nivelInArbDFS[NMAX]; // folosit si ca vizitat[]
int nivelMinVecini[NMAX];
nivelInArbDFS[0] = 0;
Biconex_fHelper(1, 0, Stiva, stVf, nivelInArbDFS, nivelMinVecini, compBic);
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::Biconex_fHelper(int nod, int parinte, pair<int, int>* Stiva, int& stVf, int* nivelInArbDFS, int* nivelMinVecini, vector<vector<int>>& compBic)
{
nivelInArbDFS[nod] = nivelInArbDFS[parinte] + 1;
nivelMinVecini[nod] = NMAX;
for (int& vecin : Adiacenta[nod])
{
if (nivelInArbDFS[vecin]) // daca e vizitat
{
if (nivelMinVecini[nod] > nivelInArbDFS[vecin] && vecin != parinte)
nivelMinVecini[nod] = nivelInArbDFS[vecin];
}
else
{
Stiva[++stVf] = {nod, vecin};
Biconex_fHelper(vecin, nod, Stiva, stVf, nivelInArbDFS, nivelMinVecini, compBic);
if (nivelMinVecini[nod] > nivelMinVecini[vecin])
nivelMinVecini[nod] = nivelMinVecini[vecin];
if (nivelMinVecini[vecin] >= nivelInArbDFS[nod])
{
compBic.push_back({});
while (Stiva[stVf].first != nod)
compBic.back().push_back(Stiva[stVf--].second);
compBic.back().push_back(Stiva[stVf].second); // muchia din 'nod', intreaga
compBic.back().push_back(Stiva[stVf].first); //
--stVf;
}
}
}
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::CompTareConexe(vector<int>* t_Adiacenta, vector<vector<int>>& compTC, int& nrComp)
{
int stivaTopo[NMAX], stVf = 0; // stivaTopo - stiva de noduri in care nodurile sunt inserate in ordinea topologica inversata
bool vizitat[NMAX];
memset(vizitat, 0, (N + 1) * sizeof(bool));
for (unsigned nod = 1; nod <= N; ++nod)
if (!vizitat[nod])
CompTareConexe_Dfs(nod, vizitat, stivaTopo, stVf);
compTC.resize(N);
nrComp = 0;
memset(vizitat, 0, (N + 1) * sizeof(bool));
while (stVf)
{
if (!vizitat[stivaTopo[stVf]])
CompTareConexe_t_Dfs(stivaTopo[stVf], vizitat, t_Adiacenta, compTC, nrComp++);
--stVf;
}
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::CompTareConexe_Dfs(int nod, bool* vizitat, int* stivaTopo, int& stVf)
{
vizitat[nod] = true;
for (auto& vecin : Adiacenta[nod])
if (!vizitat[vecin])
CompTareConexe_Dfs(vecin, vizitat, stivaTopo, stVf);
stivaTopo[++stVf] = nod;
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::CompTareConexe_t_Dfs(int nod, bool* vizitat, vector<int>* t_Adiacenta, vector<vector<int>>& compTC, int nrComp)
{
vizitat[nod] = true;
for (auto& vecin : t_Adiacenta[nod])
if (!vizitat[vecin])
CompTareConexe_t_Dfs(vecin, vizitat, t_Adiacenta, compTC, nrComp);
compTC[nrComp].push_back(nod);
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::MuchieCritica(vector<vector<int>>& mCritice)
{
int nivelInArbDFS[NMAX]; // folosit si ca vizitat[]
int nivelMin[NMAX];
memset(nivelInArbDFS, 0, (N + 1) * sizeof(int));
MuchieCritica_fHelper(0, 0, nivelInArbDFS, nivelMin, mCritice);
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::MuchieCritica_fHelper(int nod, int parinte, int* nivelInArbDFS, int* nivelMin, vector<vector<int>>& mCritice)
{
nivelInArbDFS[nod] = nivelMin[nod] = nivelInArbDFS[parinte] + 1;
for (int& vecin : Adiacenta[nod])
{
if (nivelInArbDFS[vecin])
{
if (nivelMin[nod] > nivelInArbDFS[vecin] && vecin != parinte)
nivelMin[nod] = nivelInArbDFS[vecin];
}
else
{
MuchieCritica_fHelper(vecin, nod, nivelInArbDFS, nivelMin, mCritice);
if (nivelMin[nod] > nivelMin[vecin])
nivelMin[nod] = nivelMin[vecin];
// muchie critica
if (nivelMin[vecin] > nivelInArbDFS[nod]) // nivelMin[vecin] == nivelInArbDFS[vecin]
mCritice.push_back({nod, vecin});
}
}
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::ProbGraf_NoduriComune(int X, int Y, vector<int>& noduri)
{
int lungime[NMAX]; // folosit si ca vizitat[] in BfsInainte => lungimea se calculeaza incepand de la 1
int nrVizite[NMAX]; // folosit in BfsInapoi pt a identifica unificarea ramurilor (si pentru vizitat[])
noduri.push_back(X);
// noduri.push_back(Y); -- nu e nevoie, e mereu primul adaugat in BfsInapoi
NoduriComune_BfsInainte(X, Y, lungime);
NoduriComune_BfsInapoi(X, Y, lungime, nrVizite, noduri);
sort(noduri.begin(), noduri.end());
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::NoduriComune_BfsInainte(int X, int Y, int* lungime)
{
int coada[NMAX], st = 0, dr = -1;
bool COADA_STOP_INTRARI = false;
coada[++dr] = X;
lungime[X] = 1;
while (st <= dr)
{
int nodCurent = coada[st++];
for (int& vecin : Adiacenta[nodCurent])
if (!lungime[vecin])
{
lungime[vecin] = lungime[nodCurent] + 1;
if (vecin == Y)
COADA_STOP_INTRARI = true;
if (!COADA_STOP_INTRARI)
coada[++dr] = vecin;
}
}
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::NoduriComune_BfsInapoi(int X, int Y, int* lungime, int* nrVizite, vector<int>& noduri)
{
int nrRamuri = 1; // total ramuri existente la pasul curent
int coada[NMAX], st = 0, dr = -1;
coada[++dr] = Y;
while (st <= dr)
{
int nodCurent = coada[st++];
int ramuriDinCurent = 0; // cate ramuri pornesc din nodul curent, cel putin una din moment ce avem drum mai departe
if (nrRamuri == 1)
noduri.push_back(nodCurent);
for (int& vecin : Adiacenta[nodCurent])
{
if (lungime[vecin] == lungime[nodCurent] - 1)
{
++ramuriDinCurent;
++nrVizite[vecin];
if (nrVizite[vecin] > 1)
--nrRamuri;
if (vecin == X)
break;
if (nrVizite[vecin] == 1)
coada[++dr] = vecin;
}
}
nrRamuri += (ramuriDinCurent - 1);
}
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::SortTopo(int* noduri)
{
bool vizitat[NMAX];
int dr = 0;
memset(vizitat, 0, (N + 1) * sizeof(bool));
for (unsigned nod = 1; nod <= N; ++nod)
if (!vizitat[nod])
CompTareConexe_Dfs(nod, vizitat, noduri, dr);
reverse(noduri + 1, noduri + 1 + N);
}
template<int NMAX, bool listeAdiacenta>
int Graf<NMAX, listeAdiacenta>::DiametruArbore()
{
int dist[NMAX], nodCapatLant, diametru;
Bfs(1, dist);
nodCapatLant = max_element(dist + 1, dist + N + 1) - dist;
Bfs(nodCapatLant, dist);
diametru = *max_element(dist + 1, dist + N + 1) + 1;
return diametru;
}
template<int NMAX, bool listeAdiacenta>
bool Graf<NMAX, listeAdiacenta>::HavelHakimi(int* S, int N)
{
auto descrescator = [](int a, int b) { return a > b; };
sort(S, S + N, descrescator);
if (S[0] >= N)
return false;
int grMax, pozPrimElem = 0;
while (S[pozPrimElem] > 0)
{
grMax = S[pozPrimElem++];
for (int i = pozPrimElem; i < pozPrimElem + grMax; ++i)
--S[i];
sort(S + pozPrimElem, S + N, descrescator);
if (S[N - 1] < 0)
return false;
}
return true;
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::Dijkstra(vector<vector<pair<int, int>>>& Adiacenta, int src, int INF, vector<int>& dist)
{
auto comp = [](pair<int,int>& st, pair<int,int>& dr) { return st.second > dr.second; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> heap(comp);
bool extras[NMAX];
memset(extras, 0, (N + 1) * sizeof(bool));
dist.resize(N + 1, INF);
dist[src] = 0;
heap.push({src, 0});
while (!heap.empty())
{
int nodCurent = heap.top().first;
heap.pop();
if (extras[nodCurent])
continue;
extras[nodCurent] = true;
for (auto& vecin : Adiacenta[nodCurent])
{
int nodVecin = vecin.first;
int costMuchieVecin = vecin.second;
if (dist[nodVecin] > dist[nodCurent] + costMuchieVecin)
{
dist[nodVecin] = dist[nodCurent] + costMuchieVecin;
heap.push({nodVecin, dist[nodVecin]});
}
}
}
}
template<int NMAX, bool listeAdiacenta>
bool Graf<NMAX, listeAdiacenta>::BellmanFord(vector<vector<pair<int, int>>>& Adiacenta, int src, int INF, vector<int>& dist)
{
queue<int> coadaNoduri;
unsigned nrMuchiiLant[NMAX];
bool inCoada[NMAX];
memset(inCoada, 0, (N + 1) * sizeof(bool));
nrMuchiiLant[src] = 0;
dist.resize(N + 1, INF);
dist[src] = 0;
coadaNoduri.push(src);
while (!coadaNoduri.empty())
{
int nodCurent = coadaNoduri.front();
coadaNoduri.pop();
inCoada[nodCurent] = false;
for (auto& vecin : Adiacenta[nodCurent])
{
int nodVecin = vecin.first;
int costMuchieVecin = vecin.second;
if (dist[nodVecin] > dist[nodCurent] + costMuchieVecin)
{
dist[nodVecin] = dist[nodCurent] + costMuchieVecin;
nrMuchiiLant[nodVecin] = nrMuchiiLant[nodCurent] + 1;
if (nrMuchiiLant[nodVecin] == N)
return true;
if (!inCoada[nodVecin])
{
coadaNoduri.push(nodVecin);
inCoada[nodVecin] = true;
}
}
}
}
return false;
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::RoyFloyd(vector<vector<int>>& ponderi, int INF)
{
for (unsigned i = 0; i < N; ++i)
for (unsigned j = 0; j < N; ++j)
if (ponderi[i][j] == 0 && i != j)
ponderi[i][j] = INF;
for (unsigned K = 0; K < N; ++K)
for (unsigned A = 0; A < N; ++A)
for (unsigned B = 0; B < N; ++B)
if (ponderi[A][B] > ponderi[A][K] + ponderi[K][B])
ponderi[A][B] = ponderi[A][K] + ponderi[K][B];
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::APM(vector<vector<int>>& muchiiGraf, int& costAPM, vector<pair<int, int>>& muchiiAPM)
{
// Kruskal
auto comp = [](vector<int>& m1, vector<int>& m2) { return m1[2] < m2[2]; };
sort(muchiiGraf.begin(), muchiiGraf.end(), comp);
costAPM = 0;
muchiiAPM.reserve(N - 1);
int tata[NMAX * 2], rang[NMAX * 2]; // rangurile arborilor se retin in radacini
memset(tata, 0, N * sizeof(int));
memset(rang, 0, N * sizeof(int)); // va fi inaltime - 1
auto mc = muchiiGraf.begin();
while (muchiiAPM.size() < N - 1)
{
int x = mc->at(0);
int y = mc->at(1);
int cost = mc->at(2);
int radX = Disjoint_CautaRadacina(x, tata);
int radY = Disjoint_CautaRadacina(y, tata);
Disjoint_CompresieDrumuri(x, radX, tata);
Disjoint_CompresieDrumuri(y, radY, tata);
if (radX != radY)
{
Disjoint_Reuneste(radX, radY, tata, rang);
costAPM += cost;
muchiiAPM.push_back({x, y});
}
++mc;
}
}
template<int NMAX, bool listeAdiacenta>
int Graf<NMAX, listeAdiacenta>::Disjoint_CautaRadacina(int nod, int* tata)
{
while (tata[nod])
nod = tata[nod];
return nod;
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::Disjoint_CompresieDrumuri(int nod, int radacina, int* tata)
{
while (tata[nod])
{
int old = tata[nod];
tata[nod] = radacina;
nod = tata[old];
}
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::Disjoint_Reuneste(int radX, int radY, int* tata, int* rang)
{
if (rang[radX] > rang[radY]) // fiindca rang[radX] e strict mai mare decat rang[radY],
tata[radY] = radX; // adaugarea arb. radY ca subarb. al lui radX nu va putea creste rang[radX]
else // rang[radX] <= rang[radY]
{
tata[radX] = radY;
if (rang[radY] == rang[radX]) // daca rangurile sunt egale, prin legarea rad., rangul celui de care s-a legat va creste cu 1
++rang[radY];
}
}
template<int NMAX, bool listeAdiacenta>
void Graf<NMAX, listeAdiacenta>::Disjoint(int N, vector<vector<int>>& Operatii, vector<string>& Raspuns)
{
int tata[NMAX], rang[NMAX]; // rangurile arborilor se retin in radacini
memset(tata, 0, N * sizeof(int));
memset(rang, 0, N * sizeof(int)); // va fi inaltime - 1
for (auto& op : Operatii)
{
int x = op[1];
int y = op[2];
int radX = Disjoint_CautaRadacina(x, tata);
int radY = Disjoint_CautaRadacina(y, tata);
if (op[0] == 1)
Disjoint_Reuneste(radX, radY, tata, rang);
else
{
if (radX != radY)
Raspuns.emplace_back("NU");
else
Raspuns.emplace_back("DA");
// Compresia drumurilor
Disjoint_CompresieDrumuri(x, radX, tata);
Disjoint_CompresieDrumuri(y, radY, tata);
}
}
}
template<int NMAX, bool listeAdiacenta>
int Graf<NMAX, listeAdiacenta>::FluxMaxim(int src, int dst, vector<vector<int>>& capacitati)
{
// Edmonds-Karp
vector<vector<int>> flux(NMAX, vector<int>(NMAX, 0));
int tata[NMAX], fluxMaxRetea = 0;
bool vizitat[NMAX];
memset(tata, 0, (N + 1) * sizeof(int));
while (FluxMaxim_Drum(src, dst, capacitati, flux, vizitat, tata))
{
for (int vecinDst : Adiacenta[dst])
{
if (flux[vecinDst][dst] < capacitati[vecinDst][dst] && vizitat[vecinDst])
{
int fluxMaxDrum = capacitati[vecinDst][dst] - flux[vecinDst][dst];
for (int nod = vecinDst; tata[nod]; nod = tata[nod])
{
int tataNod = tata[nod];
fluxMaxDrum = min(fluxMaxDrum, capacitati[tataNod][nod] - flux[tataNod][nod]);
}
flux[vecinDst][dst] += fluxMaxDrum;
flux[dst][vecinDst] -= fluxMaxDrum;
for (int nod = vecinDst; tata[nod]; nod = tata[nod])
{
int tataNod = tata[nod];
flux[tataNod][nod] += fluxMaxDrum;
flux[nod][tataNod] -= fluxMaxDrum;
}
fluxMaxRetea += fluxMaxDrum;
}
}
}
return fluxMaxRetea;
}
template<int NMAX, bool listeAdiacenta>
bool Graf<NMAX, listeAdiacenta>::FluxMaxim_Drum(int src, int dst, vector<vector<int>>& capacitati, vector<vector<int>>& flux, bool* vizitat, int* tata)
{
int coada[NMAX], st = 0, dr = -1;
memset(vizitat, 0, (N + 1) * sizeof(bool));
coada[++dr] = src;
vizitat[src] = true;
while (st <= dr)
{
int nodCurent = coada[st++];
for (int vecin : Adiacenta[nodCurent])
{
if (!vizitat[vecin] && flux[nodCurent][vecin] < capacitati[nodCurent][vecin])
{
vizitat[vecin] = true;
if (vecin != dst)
{
tata[vecin] = nodCurent;
coada[++dr] = vecin;
}
}
}
}
return vizitat[dst];
}
template<int NMAX, bool listeAdiacenta>
bool Graf<NMAX, listeAdiacenta>::CicluEulerian(int nodStart, vector<vector<pair<int, int>>>& lAdiacenta, vector<int>& solutie)
{
/// Hierholzer
// lAdiacenta - {nod vecin, indexul muchiei in lista nodului vecin}
// Toate gradele sunt pare?
for (unsigned i = 1; i <= N; ++i)
if (lAdiacenta[i].size() % 2)
return false;
int stiva[NMAX * 5];
stiva[0] = 1;
stiva[1] = nodStart;
while (stiva[0] > 0)
{
int nodCurent = stiva[stiva[0]];
if (lAdiacenta[nodCurent].size() > 0)
{
int nodUrmator = lAdiacenta[nodCurent].back().first;
int idxListaVecin = lAdiacenta[nodCurent].back().second;
lAdiacenta[nodCurent].pop_back();
lAdiacenta[nodUrmator][idxListaVecin] = lAdiacenta[nodUrmator].back();
lAdiacenta[nodUrmator].pop_back();
// Se actualizeaza, in lista nodului vecin, pozitia muchiei mutate
auto& nodMutat = lAdiacenta[nodUrmator][idxListaVecin];
lAdiacenta[nodMutat.first][nodMutat.second].second = idxListaVecin;
stiva[++stiva[0]] = nodUrmator;
}
else
{
solutie.push_back(nodCurent);
--stiva[0];
}
}
solutie.pop_back(); // se sterge nodul de sfarsit al ciclului (= cu primul)
if (solutie.size() != M) // muchiile nu fac parte dintr-o singura componenta conexa
return false;
return true;
}
template<int NMAX, bool listeAdiacenta>
int Graf<NMAX, listeAdiacenta>::CicluHamiltonian(int nodStart, vector<vector<unsigned>>& costMuchie, int INF)
{
const int CONFIG_MAX = 1 << N; // 1 + configuratia maxima (lant ce contine toate nodurile)
vector<vector<unsigned>> costLant(CONFIG_MAX, vector<unsigned>(N, INF));
costLant[1][0] = 0;
for (int bin = 1; bin < CONFIG_MAX; ++bin)
{
for (unsigned nod = 0; nod < N; ++nod)
{
if ((bin & (1 << nod)) != 0) // daca nodul face parte din lant (bitul nodului este 1 in configuratie)
{
for (unsigned nodVecin : Adiacenta[nod]) // graf transpus => fiecare nod care intra in nodul curent
{
if ((bin & (1 << nodVecin)) != 0)
{
unsigned costLantPrinVecin = costLant[bin ^ (1 << nod)][nodVecin] + costMuchie[nodVecin][nod];
if (costLant[bin][nod] > costLantPrinVecin)
costLant[bin][nod] = costLantPrinVecin;
}
}
}
}
}
unsigned costMinCiclu = INF;
for (auto nod : Adiacenta[nodStart])
{
unsigned costCiclu = costLant[CONFIG_MAX - 1][nod] + costMuchie[nod][nodStart];
if (costMinCiclu > costCiclu)
costMinCiclu = costCiclu;
}
return costMinCiclu;
}
template<int NMAX, bool listeAdiacenta>
bool Graf<NMAX, listeAdiacenta>::Cupleaza(int nodSt, int* perecheDr, int* perecheSt, bool* vizitat)
{
if (!vizitat[nodSt])
{
vizitat[nodSt] = true;
for (auto vecin : Adiacenta[nodSt])
if (perecheSt[vecin] == 0)
{
perecheDr[nodSt] = vecin;
perecheSt[vecin] = nodSt;
return true;
}
for (auto vecin : Adiacenta[nodSt])
if (Cupleaza(perecheSt[vecin], perecheDr, perecheSt, vizitat))
{
perecheDr[nodSt] = vecin;
perecheSt[vecin] = nodSt;
return true;
}
}
return false;
}
template<int NMAX, bool listeAdiacenta>
int Graf<NMAX, listeAdiacenta>::CuplajMaxim(vector<pair<int, int>>& cuplaj)
{
/// Hopcroft–Karp
int perecheDr[NMAX], perecheSt[NMAX];
bool vizitat[NMAX];
memset(perecheDr, 0, (N + 1) * sizeof(int));
memset(perecheSt, 0, (M + 1) * sizeof(int));
bool cuplajGasit = true;
while (cuplajGasit)
{
cuplajGasit = false;
memset(vizitat, 0, (N + 1) * sizeof(bool));
for (unsigned nodSt = 1; nodSt <= N; ++nodSt)
if (perecheDr[nodSt] == 0 && Cupleaza(nodSt, perecheDr, perecheSt, vizitat))
cuplajGasit = true;
}
int cuplajMaxim = 0;
for (unsigned nodSt = 1; nodSt <= N; ++nodSt)
if (perecheDr[nodSt])
{
++cuplajMaxim;
cuplaj.push_back({nodSt, perecheDr[nodSt]});
}
return cuplajMaxim;
}
int main()
{
ifstream f("royfloyd.in");
ofstream g("royfloyd.out");
unsigned N;
f >> N;
vector<vector<int>> ponderi(N, vector<int>(N));
for (unsigned i = 0; i < N; ++i)
for (unsigned j = 0; j < N; ++j)
f >> ponderi[i][j];
Graf<100009, false> graf(N, -1);
int INF = 9999;
graf.RoyFloyd(ponderi, INF);
for (unsigned i = 0; i < N; ++i)
{
for (unsigned j = 0; j < N; ++j)
g << (ponderi[i][j] == INF ? 0 : ponderi[i][j]) << ' ';
g << '\n';
}
return 0;
}
Ionel-Alexandru Culea Xein