Cod sursa(job #3189940)

Utilizator daria_pirvulescuPirvulescu Daria Maria daria_pirvulescu Data 6 ianuarie 2024 18:02:17
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <bits/stdc++.h>
using namespace std;
//pb6:https://www.infoarena.ro/problema/harta
ifstream fin("harta.in");
ofstream fout("harta.out");


class Graf {
public:
    int nr_noduri;
    vector<vector<int>> lista_vecini;
    vector<vector<int>> capacitati;
    vector<vector<int>> flux;


    Graf(int n) : nr_noduri(n){
        capacitati.resize(nr_noduri, vector<int>(n, 0));
        flux.resize(nr_noduri, vector<int>(n, 0));
        lista_vecini.resize(nr_noduri);
    }


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

    bool BFS(vector<int>& tati) {
        queue<int> coada;
        vector<int> vizitati(nr_noduri, 0);
        int sursa = nr_noduri ;
        int destinatie = nr_noduri ;
        coada.push(sursa);
        vizitati[sursa] = 1;

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

            for (size_t i = 0; i < lista_vecini[nod].size(); i++) {
                int vecin = lista_vecini[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 = nr_noduri - 1;
        int sursa = nr_noduri - 2;
        vector<int> tati(nr_noduri, -1);

        while (BFS(tati)) {
            int capacitateMinima = static_cast<int>(1e18);
            int nod = destinatie;

            while (nod != sursa) {
                capacitateMinima = 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 < nr_noduri; i++) {
                tati[i] = -1;
            }
        }
        return fluxMaxim;
    }


};

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

    Graf g(2 * N + 2);

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

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

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

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

    return 0;
}