Cod sursa(job #3189237)

Utilizator Apostol_AlinApostol Alin-Constantin Apostol_Alin Data 4 ianuarie 2024 18:10:30
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.99 kb
#include <bits/stdc++.h>

//https://codeforces.com/contest/450/submission/234023276

const int INF = INT_MAX;
const long long INFLONG = LLONG_MAX;
class graf{
    int nr_noduri;
    std::vector<std::vector<std::pair<int,int>>> lista_vecini;
    std::vector<std::vector<int>> matrice_adiacenta;
    std::vector<std::vector<int>> capacitati;
    std::vector<std::vector<int>> flux;
public:
    friend std::ostream& operator<<(std::ostream& os, const graf& g) {
        os << "Numar noduri: " << g.nr_noduri << "\n";
        for(int i = 0; i < g.nr_noduri; i++){
            os << i << ": ";
            for(const auto& pereche: g.lista_vecini[i])
                os << "(" << pereche.first << "," << pereche.second << ") ";
            os << "\n";
        }
        return os;
    }
    graf(int n, std::vector<std::vector<std::pair<int, int>>>& lista_vecini_) : nr_noduri(n), lista_vecini(lista_vecini_){}
    explicit graf(int n) : nr_noduri(n){
        lista_vecini.resize(nr_noduri);
        capacitati.resize(nr_noduri, std::vector<int>(n, 0));
        flux.resize(nr_noduri, std::vector<int>(n, 0));

    }
    graf(int n, std::vector<std::vector<int>>& mat) : nr_noduri(n), matrice_adiacenta(mat){}
    void adauga_muchie_orientat(int x, int y, int cost){
        lista_vecini[x].emplace_back(y,cost);
    }
    void adauga_muchie_neorientat(int x, int y, int cost){
        lista_vecini[x].emplace_back(y,cost);
        lista_vecini[y].emplace_back(x,cost);
    }
    void adauga_capacitate(int x, int y, int capacitate){
        capacitati[x][y] = capacitate;
    }
    void dijkstra(int sursa, std::vector<int>& dist, std::vector<int>& tati){
        std::set<std::pair<int,int>> set;
        set.insert(std::make_pair(0,sursa));
        dist.assign(nr_noduri, INF);
        tati.assign(nr_noduri, -1);
        dist[sursa] = 0;
        while(!set.empty()){
            int nod = set.begin()->second;
            set.erase(set.begin());
            //std::cout << nod + 1 << " " << set.begin()->first << "\n";
            for(auto& vecin: lista_vecini[nod]){
                if(dist[vecin.first] > vecin.second + dist[nod]){
                    tati[vecin.first] = nod;
                    set.erase(std::make_pair(dist[vecin.first],vecin.first));
                    dist[vecin.first] = vecin.second + dist[nod];
                    set.insert(std::make_pair(dist[vecin.first],vecin.first));
                }
            }
        }
    }
    void roy_warshall(std::vector<std::vector<int>>& dist){
        dist = matrice_adiacenta;
        int i, j, k;
        for(k = 0; k < nr_noduri; k++)
            for(i = 0; i < nr_noduri; i++)
                for(j = 0; j < nr_noduri; j++){
                    if (dist[i][j] > (dist[i][k] + dist[k][j])  && (dist[k][j] != INF && dist[i][k] != INF))
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
    }
    void prim(int root, std::vector<int>& dist, std::vector<int>& tati, int& total_dist){
        std::set<std::pair<int, int>> set;
        std::vector<int> viz(nr_noduri, 0);
        set.insert(std::make_pair(0, root));
        dist.assign(nr_noduri, INF);
        tati.assign(nr_noduri, -1);
        dist[root] = 0;
        viz[root] = 0;
        total_dist = 0;
        while(!set.empty()){
            int nod = set.begin()->second;
            set.erase(set.begin());
            //std::cout << nod << " " << dist[nod] << "\n";
            total_dist += dist[nod];
            viz[nod] = 1;
            for(auto& vecin: lista_vecini[nod]){
                if(dist[vecin.first] > vecin.second and viz[vecin.first] == 0){
                    tati[vecin.first] = nod;
                    set.erase(std::make_pair(dist[vecin.first],vecin.first));
                    dist[vecin.first] = vecin.second;
                    set.insert(std::make_pair(dist[vecin.first],vecin.first));
                }
            }
        }
    }
    static std::vector<int> path(int sursa, int dest, const std::vector<int>& tati){
        std::vector<int> drum;
        int curent = sursa;
        drum.push_back(sursa);
        while(tati[curent] != dest){
            curent = tati[curent];
            drum.push_back(curent);
        }
        drum.push_back(dest);
        return drum;
    }

    bool bfs_for_flux(std::vector<int>& tati)
    {
        std::queue<int> coada;
        std::vector<int> vizitati(nr_noduri, 0);
        coada.push(nr_noduri - 2); // plecam din sursa
        vizitati[nr_noduri - 2] = 1;
        while(!coada.empty()){
            int nod = coada.front();
            coada.pop();
            for(int i = 0; i < nr_noduri; i++){
                if(vizitati[i] == 0 and (capacitati[nod][i] - flux[nod][i] > 0)){
                    coada.push(i);
                    tati[i] = nod;
                    vizitati[i] = 1;
                }
            }
        }
        return vizitati[nr_noduri - 1]; //returnam daca putem ajunge la destinatie
    }
    int flux_maxim(){
        int flux_maxim = 0;
        int destinatie = nr_noduri - 1; //2 * n + 1
        int sursa = nr_noduri - 2; //2 * n
        std::vector<int> tati(nr_noduri, -1);
        while(bfs_for_flux(tati)){
            int capacitate_minima = INF;
            int nod = destinatie;
            while(nod != sursa){
                capacitate_minima = std::min(capacitati[tati[nod]][nod] - flux[tati[nod]][nod], capacitate_minima);
                nod = tati[nod];
            }
            flux_maxim += capacitate_minima;
            nod = destinatie;
            while(nod != sursa){
                flux[tati[nod]][nod] += capacitate_minima;
                flux[nod][tati[nod]] -= capacitate_minima;
                nod = tati[nod];
            }
            tati.clear();
            tati.assign(nr_noduri, -1);
        }
        return  flux_maxim;
    }
    std::vector<std::vector<int>> get_flux() const {
        return flux;
    }

};

int main() {
    int n, x, y;
    std::ifstream fin("harta.in");
    fin >> n;
    graf g{2 * n + 2};
    for(int i = 0 ; i < n ; i++){
        fin >> x >> y;
        g.adauga_capacitate(2 * n, i, x); //Nodul 2 * n este nodul de start
        //din acest nod pleaca in fiecare nod un drum care are capacitatea x
        //adica cate muchii trebuie sa intre in nodul i
        //apoi din nodul i + n pleaca in nodul 2 * n + 1 (destinatia) un drum care are capacitatea y
        //adica cate muchii trebuie sa iasa din nodul i + n
        //nodul i + n si i sunt "acelasi nod despartit in doua"
        //apoi stim ca dintr-un nod x putem avea o singura muchie in nodul y (x != y)
        //asta inseamna o capacitate de 1
        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();
    std::ofstream fout("harta.out");
    fout << g.flux_maxim() << '\n';
    std::vector<std::vector<int>> rez = g.get_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;
}