Cod sursa(job #2960684)

Utilizator woodyinhoStoica Elias-Valeriu woodyinho Data 4 ianuarie 2023 20:19:36
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

vector<vector<int>> graf;
vector<int> vizitat;
vector<int> tata;
vector<vector<int>> capacitate;
vector<vector<int>> flux;

int n, sursa, dest;

void bfs(){
    fill(vizitat.begin(), vizitat.end(), 0);
    queue<int> coada;
    coada.push(sursa);
    vizitat[sursa] = 1;

    while(!coada.empty()){
        int nod = coada.front();
        coada.pop();
        if(nod == dest)
            continue;
        for(auto &vecin:graf[nod]){
            if(capacitate[nod][vecin] == flux[nod][vecin] || vizitat[vecin] == 1)
                continue;
            vizitat[vecin] = 1;
            tata[vecin] = nod;
            coada.push(vecin);
        }
    }
}

int fluxMaxim(){
    int maxFlux = 0;
    //facem bfs cat timp mai exista drumuri de la sursa la destinatie pe care sa le verificam pentru fluxul maxim
    bfs();
    //cout<<"dupa bfs";
    while(vizitat[dest] == 1){
        //daca am ajuns la destinatie, inseamna ca am gasit un nou drum si verificam fluxul maxim pe acest drum
        for(auto vecin: graf[dest]){
            if(capacitate[vecin][dest] == flux[vecin][dest]) //daca nu mai am capacitate pe muchia respectiva, nu o mai verific
                continue;
            tata[dest] = vecin;

            //memoram cat mai putem sa adaugam pe acest drum
            //sunt sanse ca din cauza ordinei in care am luat drumurile, unul din drumuri sa nu ajunga la capacitatea maxima, fiind
            //blocat de un alt drum
            int minim = capacitate[tata[dest]][dest] - flux[tata[dest]][dest];
            vecin = tata[dest];
            while(vecin != sursa){
                minim = min(capacitate[tata[vecin]][vecin] - flux[tata[vecin]][vecin], minim);
                vecin = tata[vecin];
            }

            //la final avem in minim cat mai putem sa adaugam pe acest drum
            vecin = dest;
            while(vecin != sursa){
                //adaugam
                flux[tata[vecin]][vecin] += minim;
                flux[vecin][tata[vecin]] -= minim;
                vecin = tata[vecin];
            }

            maxFlux += minim;

        }
        bfs();
        //cout<<"dupa alt bfs\n";
        //cout<<maxFlux;
        //cout<<"\n";
    }
    return maxFlux;
}

int main() {

    f>>n;
    sursa = 0;
    dest = 2 * n + 1;
    int nr_noduri_graf = 2 * n + 2;
    graf.resize(nr_noduri_graf);
    vizitat.resize(nr_noduri_graf);
    tata.resize(nr_noduri_graf); //tata[i] = nodul din care am ajuns in nodul i
    capacitate.resize(nr_noduri_graf, vector<int>(nr_noduri_graf, 0)); //capacitatea de pe muchia (i, j)
    flux.resize(nr_noduri_graf, vector<int>(nr_noduri_graf, 0)); //fluxul de pe muchia (i, j)

    for(int i = 1; i <= n; i++){
        int grad_in, grad_out; //grad_in = numarul de muchii care intra in nodul i, grad_out = numarul de muchii care ies din nodul i
        f>>grad_out>>grad_in;
        capacitate[sursa][i] = grad_out;
        capacitate[i + n][dest] = grad_in;
        graf[sursa].push_back(i);
        graf[i + n].push_back(dest);
        graf[i].push_back(sursa);
        graf[dest].push_back(i + n);
        for(int j = 1; j <= n; j++){
            if(i!=j)
            {
                capacitate[i][j + n] = 1;
                graf[i].push_back(j + n);
                graf[j + n].push_back(i);
            }
        }
    }

    g<<fluxMaxim()<<"\n";

    //nodurile cuplate sunt cele care au fluxul maxim pe muchia (i, j) = capacitatea de pe muchia (i, j)
    //muchiile respective nu sunt adiacente nici cu sursa, nici cu destinatia

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(capacitate[i][j + n] == flux[i][j + n] && i != j){
                g<<i<<" "<<j<<"\n";
            }
        }
    }
    return 0;
}