Cod sursa(job #3186422)

Utilizator Farcasi_George_OctavianFarcasi George Octavian Farcasi_George_Octavian Data 23 decembrie 2023 00:16:19
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

class Graf{
    vector<vector<int>>matrice_adiac;
    int nr_noduri;
    bool orientat = true;
public:
    Graf() = default;

    Graf(int nr_noduri, bool orientat = true) : nr_noduri(nr_noduri), orientat(orientat){
        matrice_adiac=vector<vector<int>>(nr_noduri,vector<int>(nr_noduri,0));
    };

    vector<vector<int>>&get_matrice(){
        return matrice_adiac;
    }

    void add_muchie(int i, int j, int capacitate){
        matrice_adiac[i][j] = capacitate;
        if(!orientat)
            matrice_adiac[j][i] = capacitate;
    };

    void printare(){
        for(int i=0;i<nr_noduri;i++) {
            for (int j = 0; j < nr_noduri; j++)
                cout << matrice_adiac[i][j]<<" ";
            cout<<"\n";
        }
    }
};

class Solutii{

    bool bfs(const vector<vector<int>>&matrice_adiac, vector<int>&parinti, const int sursa, const int terminal, const int nr_noduri){

        int curent = sursa;
        queue<int>coada;
        bool vizitat[nr_noduri];
        for(auto &elem:vizitat)
            elem = false;

        coada.push(curent);
        vizitat[curent]=true;
        while(!coada.empty()) {
            curent = coada.front();
            coada.pop();

            for (int vecin = 0; vecin < nr_noduri; vecin++) {
                if (matrice_adiac[curent][vecin] > 0 && !vizitat[vecin]) {
                    coada.push(vecin);
                    vizitat[vecin] = true;
                    parinti[vecin] = curent;
                }

            }
        }
        if(vizitat[terminal])
            return true;
        return false;
    };

public:

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

        int nr_noduri,a,b;
        f>>nr_noduri;

        Graf graf(2*nr_noduri+2); //nodul sursa si nodul destinatie adaugate in plus

        for(int i=1;i<=nr_noduri;i++){

            f>>a>>b;
            graf.add_muchie(0,i,a);
            graf.add_muchie(i+nr_noduri,2*nr_noduri+1,b);

            for(int j=1;j<=nr_noduri;j++){
                if(i==j)
                    continue;
                graf.add_muchie(i,j+nr_noduri,1);
            }
        }


        vector<int>parinti(2*nr_noduri+2,-1);
        vector<pair<int,int>>res;
        vector<vector<int>>matrice=graf.get_matrice();

        //graf.printare();cout<<"\n\n";

        while(bfs(matrice,parinti,0,nr_noduri+1, 2*nr_noduri+2)){
            //for(auto elem : parinti)
                //cout<<elem<<" ";cout<<"\n";
            int cap_min = INT_MAX, v = 2*nr_noduri+1, tata,x,y=parinti[v];
            while(v){
                tata = parinti[v];
                cap_min = min(cap_min, matrice[tata][v]);
                x=v;
                v=parinti[v];
            }
            res.push_back({x,y});
           // cout<<cap_min<<"\n";

            v = 2*nr_noduri+1;
            while(v){
                tata = parinti[v];
                matrice[tata][v] -= cap_min;
                matrice[v][tata] += cap_min;
                v=parinti[v];
            }
        }

        //graf.printare();

        g<<res.size()<<"\n";
        for(auto &elem:res)
            g<<elem.first<<" "<<elem.second<<"\n";


    }

};


int main() {

    Solutii s;
    /*
    vector<int> parinti(6,-1);
    vector<vector<int>> matrice_adiac{
            vector<int>{0, 8, 0, 0, 3, 0},
            vector<int>{0, 0, 9, 0, 0, 0},
            vector<int>{0, 0, 0, 0, 7, 2},
            vector<int>{0, 0, 0, 0, 0, 5},
            vector<int>{0, 0, 7, 4, 0, 0},
            vector<int>{0, 0, 0, 0, 0, 0}
    };

    cout<<s.bfs(matrice_adiac,parinti,0,2,6)<<"\n";

    for(auto elem : parinti)
        cout<<elem<<" ";
    */
    s.harta();

    return 0;
}