Cod sursa(job #3186445)

Utilizator Farcasi_George_OctavianFarcasi George Octavian Farcasi_George_Octavian Data 23 decembrie 2023 01:23:04
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.39 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)){
            //cout<<"te pup";
//            for(auto elem : parinti)
//                cout<<elem<<" ";cout<<"\n";
            int cap_min = INT_MAX, v = 2*nr_noduri+1, tata, de_sters1=-1, de_sters2=-1;
            while(v){
                tata = parinti[v];
                cap_min = min(cap_min, matrice[tata][v]);

                if(tata < v) {
                    if (v != 2 * nr_noduri + 1 && tata)
                        res.push_back({tata, v - nr_noduri});
                }
                else{
                    de_sters1 = v;
                    de_sters2 = tata-nr_noduri;
                }
                v=parinti[v];
            }

            if(de_sters1!=-1){
                vector<pair<int,int>>::iterator i = res.begin();
                for(;i!=res.end();i++)
                    if(i->first == de_sters1 && i->second == de_sters2)
                        break;
                res.erase(i);
//                auto it = find(res.begin(),res.end(),pair{de_sters1,de_sters2});
//                if(it!=res.end())
//                    res.erase(it);
            }
            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;
}