Pagini recente » Cod sursa (job #2050460) | Cod sursa (job #3277414) | Cod sursa (job #2476956) | Cod sursa (job #2376066) | Cod sursa (job #2967906)
// Complexitate: O(n * m^2)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, in[101], out[101], capGrafRezidual[202][202], newSource, newDestination, tata[202];
vector<int> listaAdiacenta[202];
bool bfs() {
vector<bool> vizitat;
queue<int> q;
vizitat.resize(newDestination + 1);
q.push(newSource);
vizitat[newSource] = true;
while(!q.empty()){
int nod = q.front();
q.pop();
for(auto vecin : listaAdiacenta[nod]){
// Daca vecinul nu e vizitat si se poate adauga flow pe muchia de la nod la el (capacitatea e mai mare decat 0)
if(!vizitat[vecin] && capGrafRezidual[nod][vecin]){
// Este updatat vectorul tata pentru a putea reconstrui drumul de ameliorare
tata[vecin] = nod;
vizitat[vecin] = true;
q.push(vecin);
// Daca vecinul este destinatia atunci am gasit un drum bun
// BFS-ul este optimizat pentru ca el se incide direct cand vecinul este destinatia
if(vecin == newDestination)
return true;
}
}
}
return false;
}
int edmondsKarp()
{
int raspuns = 0;
// Cat timp mai gasesc un drum pana la destinatie pe care pot adauga flow
while(bfs()) {
int nod = newDestination, bottleNeck = 1000000000;
while(nod != newSource) {
int parinte = tata[nod];
if(capGrafRezidual[parinte][nod] < bottleNeck) {
// Este calculata valoarea minima de pe drumul respectiv (bottleNeck), de la destinatie la sursa
// folosind vectorul tata
bottleNeck = capGrafRezidual[parinte][nod];
}
nod = parinte;
}
// Adaug la toate muchiile de pe drum flow-ul maxim
nod = newDestination;
while(nod != newSource) {
int parinte = tata[nod];
capGrafRezidual[parinte][nod] -= bottleNeck; // Drum direct in graful rezidual
capGrafRezidual[nod][parinte] += bottleNeck; // Drum invers in graful rezidual
nod = parinte;
}
// Adaug flow-ul gasit la raspuns
raspuns += bottleNeck;
}
return raspuns;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> in[i] >> out[i];
newSource = 0;
newDestination = 2 * n + 1;
// Muchiile intermediare
// Nodurile sunt trecute in 2 multimi, una care e conectata de sursa si una care e conectata de destinatie
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(i != j) {
listaAdiacenta[i].push_back(n + j);
listaAdiacenta[n + j].push_back(i);
capGrafRezidual[i][n + j] = 1;
}
// Muchii de la sursa la nodurile din prima multime
for(int i = 1; i <= n; ++i) {
listaAdiacenta[newSource].push_back(i);
capGrafRezidual[newSource][i] = in[i]; // gradele de iesire
}
// Muchii de la noduri la destinatie
for(int i = 1; i <= n; ++i) {
listaAdiacenta[n + i].push_back(newDestination);
capGrafRezidual[n + i][newDestination] = out[i]; //gradele de intrare
}
fout << edmondsKarp() << '\n';
//Muchiile construite
// Arcele care au flux pozitiv sunt muchiile construite
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(capGrafRezidual[n+j][i] == 1)
fout << i << " " << j << '\n';
/*
Există graf cu secvenţele date <=> în rețeaua asociată fluxul de valoare maximă are
val(f)=𝑑1+ + ... + 𝑑𝑛+ = 𝑑1− + ... + 𝑑𝑛− (saturează toate arcele care ies din s și toate arcele care intră în t )
tăieturile({s},V-{s}),(V-{t},{t})sunt minime
*/
return 0;
}