Cod sursa(job #2962445)

Utilizator AncaGAncuta Gava AncaG Data 8 ianuarie 2023 16:39:18
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.36 kb
#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(202, false);
    parinte.assign(202, -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 (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 (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);
        parinte.resize(n+1);
        vizitat.resize(n+1, false);
        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;
    }