Cod sursa(job #3190650)

Utilizator raresp19Papusoi Rares raresp19 Data 7 ianuarie 2024 19:51:19
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 11.12 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <stack>
#include <map>
#include <unordered_map>
#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(int n) {
        this->listeAdiacenta = vector<vector<int>>(n);
        this->capacitate = vector<vector<int>>(n, vector<int>(n));
        this->flux = vector<vector<int>>(n, vector<int>(n));
    }

    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));
    }

    void adaugaMuchie(int start, int destinatie, int capacitate) {
        listeAdiacenta[start].push_back(destinatie);
        listeAdiacenta[destinatie].push_back(start);
        this->capacitate[start][destinatie] = capacitate;
    }

    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<int> intersectii(const int& start) {
        vector<int> vizitati(capacitate.size(), 0);

        vizitati[start] = 1;
        queue<int> q;
        q.push(start);
        while (!q.empty()) {
            int nodCurent = q.front();
            q.pop();

            for (int vecin : listeAdiacenta[nodCurent]) {
                if (!vizitati[vecin] && capacitate[nodCurent][vecin] > flux[nodCurent][vecin]) {
                    vizitati[vecin] = 1;
                    q.push(vecin);
                }
            }
        }

        return vizitati;
    }

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


};

class Solutie {
    void dfs(string aeroport, map<string, priority_queue<string, vector<string>, greater<string>>>& graf, 
             vector<string>& itinerariu) {
        while (!graf[aeroport].empty()) {
            string urmator = graf[aeroport].top();
            graf[aeroport].pop();
            dfs(urmator, graf, itinerariu);
        }
        itinerariu.push_back(aeroport);
    }
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';
            }
        }
    }

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

        int n, m;
        string linie;
        f>>n>>m;
        vector<vector<int>> listeAdiacenta(n+m+2);
        vector<vector<int>> capacitate(n+m+2, vector<int>(n+m+2, 0));

        for (int i=1; i<=n; i++) {
            f>>linie;
            for (int j=0; j<m; j++) {
                if (linie[j] == '1') {
                    listeAdiacenta[i].push_back(n+j+1);
                    listeAdiacenta[n+j+1].push_back(i);
                    capacitate[i][n+j+1] = 1;
                }
            }
        }

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

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

        Graf graf(listeAdiacenta, capacitate);

        graf.fluxMaxim(0, n+m+1);

        vector<int> intersectii = graf.intersectii(0);

        for (int i=0; i<n; i++) {
            if (!intersectii[i+1]) {
                g<<char('A' + i);
            }
        }

        for (int i=n+1; i<n+m+1; i++) {
            if (intersectii[i]) {
                g<<char('a' + i - n - 1);
            }
        }

    }

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

        string linie;
        int n, m;
        f>>n>>m;
        vector<vector<int>> listaAdiacenta(n + m + 2);
        vector<vector<int>> capacitati(n + m + 2, vector<int>(n + m + 2, 0));
        getline(f, linie);

        for (int i=1; i<=m; i++) {
            getline(f, linie);

            int nr = 0;
            for (int j=0; j<linie.size(); j++) {
                if (linie[j] != ' ') {
                    nr = nr * 10 + (linie[j] - '0');
                }
                else {
                    listaAdiacenta[nr].push_back(n + i);
                    listaAdiacenta[n + i].push_back(nr);
                    capacitati[nr][n + i] = 1;
                    nr = 0;
                }
            }
            if (nr != 0) {
                listaAdiacenta[nr].push_back(n + i);
                listaAdiacenta[n + i].push_back(nr);
                capacitati[nr][n + i] = 1;
            }
        }

        for (int i=1; i<=n; i++) {
            listaAdiacenta[0].push_back(i);
            listaAdiacenta[i].push_back(0);
            capacitati[0][i] = 1;
        }

        for (int i=n+1; i<=n+m; i++) {
            listaAdiacenta[i].push_back(n+m+1);
            listaAdiacenta[n+m+1].push_back(i);
            capacitati[i][n+m+1] = 1;
        }

        Graf graf(listaAdiacenta, capacitati);
        int flux = graf.fluxMaxim(0, n+m+1);

        if (flux != m)
            g<<0;
        else {
            for (int i=n+1; i<=n+m; i++) {
                for (int j=1; j<=n+1; j++) {
                    if (graf.getFlux()[j][i]) {
                        g<<j<<"\n";
                    }
                }
            }
        }

    }

    void Soldati() {
        int n, m;
        cin >> n >> m;

        vector<int> ai(n), bi(n);
        for (int& a : ai) cin >> a;
        for (int& b : bi) cin >> b;

        if (accumulate(ai.begin(), ai.end(), 0) != accumulate(bi.begin(), bi.end(), 0)) {
            cout << "NO\n";
            return;
        }


        Graf graf(2 * n + 2);
        int totalBi = accumulate(bi.begin(), bi.end(), 0);

        for (int i = 0; i < n; ++i) {
            graf.adaugaMuchie(0, i + 1, bi[i]);
            graf.adaugaMuchie(i + 1, n + i + 1, ai[i]);
            graf.adaugaMuchie(n + i + 1, 2 * n + 1, ai[i]);
        }

        for (int i = 0; i < m; ++i) {
            int p, q;
            cin >> p >> q;
            graf.adaugaMuchie(p, n + q, INT_MAX);
            graf.adaugaMuchie(q, n + p, INT_MAX);
        }

        int flow = graf.fluxMaxim(0, 2 * n + 1);
        if (flow < totalBi) {
            cout << "NO\n";
            return;
        }


        cout << "YES\n";
        vector<vector<int>> flux = graf.getFlux();
        for (int i = 1; i <= n; ++i) {
            int soldiers_staying = flux[i][n + i]; 

            for (int j = 1; j <= n; ++j) {
                if (i == j) {
                    cout << soldiers_staying << ' '; 
                } else {
                    cout << -flux[n + i][j] << ' ';
                }
            }
            cout << '\n';
        }
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        map<string, priority_queue<string, vector<string>, greater<string>>> graf;
        vector<string> itinerariu;

        for (auto& bilet : tickets) {
            graf[bilet[0]].push(bilet[1]);
        }

        dfs("JFK", graf, itinerariu);

        reverse(itinerariu.begin(), itinerariu.end());

        return itinerariu;
    }

    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        unordered_map<int, stack<int>> graf;
        unordered_map<int, int> grad;
        stack<int> drum;
        vector<vector<int>> rezultat;

        for (auto& pereche : pairs) {
            graf[pereche[0]].push(pereche[1]);
            grad[pereche[0]]++;
            grad[pereche[1]]--;
        }

        int start = pairs[0][0];
        for (auto& gr : grad) {
            if (gr.second > 0) {
                start = gr.first;
                break;
            }
        }

        drum.push(start);
        while (!drum.empty()) {
            int nod = drum.top();
            if (!graf[nod].empty()) {
                drum.push(graf[nod].top());
                graf[nod].pop();
            } else {
                drum.pop();
                if (!drum.empty()) {
                    rezultat.push_back({drum.top(), nod});
                }
            }
        }

        reverse(rezultat.begin(), rezultat.end());
        return rezultat;
    }
};

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