Cod sursa(job #3188992)

Utilizator raresp19Papusoi Rares raresp19 Data 4 ianuarie 2024 12:37:04
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.57 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <vector>
#include <climits>

using namespace std;

class Graf {
    vector<vector<int>> listeAdiacenta;
    vector<vector<int>> flux;
    vector<vector<int>> capacitate;


    int bfs(const int& sursa, const int& destinatie, vector<int>& parinte) {
        for (int i=0; i<parinte.size(); i++ ){
            parinte[i] = -1;
        }

        parinte[sursa] = -2;
        queue<pair<int, int>> q;
        q.push({sursa, INT_MAX});

        while (!q.empty()) {
            int nodCurent = q.front().first;
            int fluxCurent = q.front().second;
            q.pop();

            for (int vecin : listeAdiacenta[nodCurent]) {
                if (parinte[vecin] == -1 && capacitate[nodCurent][vecin] > flux[nodCurent][vecin]) {
                    parinte[vecin] = nodCurent;
                    int fluxMinim = min(fluxCurent, capacitate[nodCurent][vecin] - flux[nodCurent][vecin]);
                    if (vecin == destinatie) {
                        return fluxMinim;
                    }
                    q.push({vecin, fluxMinim});
                }
            }
        }

        return 0;
    }
public:

    Graf(vector<vector<int>>& listeAdiacenta, vector<vector<int>>& capacitate) {
        this->listeAdiacenta = listeAdiacenta;
        this->capacitate = capacitate;
        flux = vector<vector<int>>(capacitate.size(), vector<int>(capacitate.size(), 0));
    }

    int fluxMaxim(const int& sursa, const int& destinatie) {
        vector<int> parinte(capacitate.size(), -1); 
        int fluxMaxim = 0;

        while(true) {
            int fluxGasit = bfs(sursa, destinatie, parinte);
            if (!fluxGasit) {
                break;
            }

            fluxMaxim += fluxGasit;
            int nodCurent = destinatie;
            while(nodCurent != sursa) {
                int parinteNodCurent = parinte[nodCurent];
                flux[parinteNodCurent][nodCurent] += fluxGasit;
                flux[nodCurent][parinteNodCurent] -= fluxGasit;
                nodCurent = parinteNodCurent;
            }
        }

        return fluxMaxim;
    }

    vector<vector<int>> getFlux() {
        return flux;
    }


};

class Solutie {
public:
    void Harta() {
        ifstream f("harta.in");
        ofstream g("harta.out");

        int n, x, y;
        f>>n;

        vector<vector<int>> listeAdiacenta(n+n+2);
        vector<vector<int>> capacitate(n+n+2, vector<int>(n+n+2, 0));

        for (int i=1; i<=n; i++) {
            f>>x>>y;

            listeAdiacenta[0].push_back(i);
            listeAdiacenta[i].push_back(0);
            capacitate[0][i] = x;

            listeAdiacenta[n+i].push_back(n+n+1);
            listeAdiacenta[n+n+1].push_back(n+i);
            capacitate[n+i][n+n+1] = y;
        }

        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                if (i == j) 
                    continue;
                listeAdiacenta[i].push_back(n+j);
                listeAdiacenta[n+j].push_back(i);
                capacitate[i][n+j] = 1;
            }
        }

        Graf graf(listeAdiacenta, capacitate);

        int fluxMaxim = graf.fluxMaxim(0, n+n+1);

        g<<fluxMaxim<<'\n';

        for (int i=1; i<=n; i++) {
            for (int j=n+1; j<=n+n; j++) {
                if (graf.getFlux()[i][j])
                    g<<i<<' '<<j-n<<'\n';
            }
        }
    }
};

int main() {
    Solutie s;
    s.Harta();
    return 0;
}