Pagini recente » Cod sursa (job #2353370) | Cod sursa (job #2790055) | Cod sursa (job #1122891) | Cod sursa (job #1714569) | Cod sursa (job #2962452)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
vector<vector<int>> graf_artificial;
vector<int> parinte;
vector<bool> vizitat;
// Cum am gandit: ... precum indicatiile de la laborator si curs
// adăugăm un nod de start, un nod de terminal construind un graf artificial
// folosim nodurile construind 2 multimi pe care le legam intre ele prin muchii
// (in afara de situatia nodului cu el insusi--> cu indici identici)
// left e cu nodul start legata si right e co nodul destinatie legata
// punem fluxul pe muchii
// apoi avem flux maxim, iar in final ne intereseaza muchiile saturate pt afisarea drumurilor
// Complexitate O(m^2)
bool bfs_taram(int n) {
queue <int> q_bfs;
q_bfs = queue <int> ();
vizitat.assign(n+1, false);
parinte.assign(n+1, -1);
q_bfs.push(0);
vizitat[0] = true;
while (!q_bfs.empty()) {
int nod_curent = q_bfs.front();
q_bfs.pop();
for (int i = 0; i <= n; i++) {
if (graf_artificial[nod_curent][i] > 0 && !vizitat[i]) {
q_bfs.push(i);
vizitat[i] = true;
parinte[i] = nod_curent;
if (i == n) { // daca am ajuns la destinatie
return true;
}
}
}
}
return false; // daca nu am gasit path
}
int fluxMaxim(int n) {
int flux_max = 0;
while (bfs_taram(n)) {
for (int nod = 1; nod < n; ++nod) {
// verifica saturarea muchiilor si nevizitarea nodurilor
if (graf_artificial[nod][n] > 0 && vizitat[nod]) {
vector<int> path;
int flux = INT_MAX;
path.push_back(n);
path.push_back(nod);
int prev = parinte[nod];
// merg din parinte in parinte pana la sursa
while (prev != -1) {
path.push_back(prev);
prev = parinte[prev];
}
// merg consecutiv din parinte in parinte de-a lungul path-ului
for (unsigned int v = 1; v < path.size(); ++v)
flux = min(flux, graf_artificial[path[v]][path[v - 1]]);
// calcul flux
flux_max += flux;
// am partea de updatare de flux in cadrul grafului rezidual
for (unsigned int v = 1; v < path.size(); ++v) {
graf_artificial[path[v]][path[v - 1]] -= flux;
graf_artificial[path[v - 1]][path[v]] += flux;
}
}
}
}
return flux_max;
}
int main() {
ifstream f_cin ("harta.in");
ofstream f_cout ("harta.out");
int n;
f_cin >> n;
vector<vector<int>> grade;
grade.resize(n + 1);
graf_artificial.resize(2*n+2, vector<int>(2*n+2, 0));
for (int i = 1; i <= n; i++) {
int grade_in, grade_out;
f_cin >> grade_out >> grade_in;
grade[i] = {grade_out, grade_in}; //un vector de un tupluri cu gradele de intrare si iesire
}
f_cin.close();
// avem 2*n + 2 dar minus 1 pentru ca indexarea incepe de la 0 (pt val nodului destinatie)
for (int i = 1; i <= n; i++) {
graf_artificial[0][i] = grade[i][0]; // pt flux pe left iau fradele de iesire
graf_artificial[i + n][2 * n + 1] = grade[i][1]; // pt flux pe right iau gradele de intrare
}
// adaugare flux 1 pe nodurile dintre left si right
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j) // cu exceptia nodului cu el insusi
graf_artificial[i][n + j] = 1; // i merge pe left ca noduri si de la n+j am val nodurilor pe right
f_cout << fluxMaxim(2 * n + 1) <<endl;
for (int i = 1; i <= n; ++i)
for (int j = n + 1; j <= 2* n; ++j) // iau de la capat ca sa afisez last end point pe drumul repsectiv
if (graf_artificial[j][i] != 0) // pt afisare am muchiile saturate(adica fluxul invers de decrementare pe rezidual e dif de 0)
f_cout << i << " " << j - n <<endl;
return 0;
}