Cod sursa(job #3189816)

Utilizator mariapreda19Preda Maria mariapreda19 Data 6 ianuarie 2024 15:48:24
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <fstream>
#include <vector>
#include <queue>

std::ifstream fin("harta.in");
std::ofstream fout("harta.out");


class Graf {
    int numarNoduri;
    std::vector<std::vector<int>> listaAdiacenta;
    std::vector<std::vector<int>> capacitati;
    std::vector<std::vector<int>> flux;

public:
    explicit Graf(int numarNoduri) : numarNoduri(numarNoduri) {
        listaAdiacenta.resize(numarNoduri);
        capacitati.resize(numarNoduri);
        for(int i = 0; i < numarNoduri; i++)
            capacitati[i].resize(numarNoduri, 0);
        flux.resize(numarNoduri);
        for(int i = 0; i < numarNoduri; i++)
            flux[i].resize(numarNoduri, 0);
    }

    void adaugaCapacitate(int x, int y, int capacitate) {
        listaAdiacenta[x].push_back(y);
        listaAdiacenta[y].push_back(x);
        capacitati[x][y] = capacitate;
    }

    bool bfsForFlux(std::vector<int>& tati) {
        std::queue<int> coada;
        std::vector<int> vizitati(numarNoduri, 0);
        int sursa = numarNoduri - 2;
        int destinatie = numarNoduri - 1;
        coada.push(sursa);
        vizitati[sursa] = 1;

        while (!coada.empty()) {
            int nod = coada.front();
            coada.pop();

            for (int i = 0; i < listaAdiacenta[nod].size(); i++) {
                int vecin = listaAdiacenta[nod][i];
                if (vizitati[vecin] == 0 && (capacitati[nod][vecin] - flux[nod][vecin] > 0)) {
                    coada.push(vecin);
                    tati[vecin] = nod;
                    vizitati[vecin] = 1;
                }
            }
        }
        return vizitati[destinatie];
    }

    int fluxMaxim() {
        int fluxMaxim = 0;
        int destinatie = numarNoduri - 1;
        int sursa = numarNoduri - 2;
        std::vector<int> tati(numarNoduri, -1);

        while (bfsForFlux(tati)) {
            int capacitateMinima = INT_MAX;
            int nod = destinatie;

            while (nod != sursa) {
                capacitateMinima = std::min(capacitati[tati[nod]][nod] - flux[tati[nod]][nod], capacitateMinima);
                nod = tati[nod];
            }

            fluxMaxim += capacitateMinima;
            nod = destinatie;

            while (nod != sursa) {
                flux[tati[nod]][nod] += capacitateMinima;
                flux[nod][tati[nod]] -= capacitateMinima;
                nod = tati[nod];
            }

            for (int i = 0; i < numarNoduri; i++) {
                tati[i] = -1;
            }
        }
        return fluxMaxim;
    }

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

int main() {
    int numarNoduri, x, y;
    fin >> numarNoduri;

    Graf g(2 * numarNoduri + 2);

    for (int i = 0; i < numarNoduri; i++) {
        fin >> x >> y;
        g.adaugaCapacitate(2 * numarNoduri, i, x);
        g.adaugaCapacitate(i + numarNoduri, 2 * numarNoduri + 1, y);

        for (int j = 0; j < numarNoduri; j++) {
            if (i != j)
                g.adaugaCapacitate(i, j + numarNoduri, 1);
        }
    }
    fin.close();

    fout << g.fluxMaxim() << '\n';

    std::vector<std::vector<int>> rez = g.getFlux();
    for (int i = 0; i < numarNoduri; i++) {
        for (int j = 0; j < numarNoduri; j++) {
            if (rez[i][j + numarNoduri] == 1)
                fout << i + 1 << ' ' << j + 1 << '\n';
        }
    }
    fout.close();

    return 0;
}