Cod sursa(job #3190914)

Utilizator sad_carrotVisan Sebastian sad_carrot Data 8 ianuarie 2024 13:09:18
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <deque>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

class Graph{
    int n, nr_noduri, s, t;
    int infinity = 1e8;
    vector<int> parent;
    vector<unordered_map<int, int>> adiac;
public:
    Graph(){
        f >> n;
        nr_noduri = 2 * n + 2;
        s = nr_noduri - 2;
        t = nr_noduri - 1;
        adiac.resize(nr_noduri);
        int intrare, iesire;
        for(int i = 0; i < n; i++){
            f >> intrare >> iesire;
            intrare; iesire;
            adiac[s][i] = intrare;
            adiac[i + n][t] = iesire;
            for(int j = 0; j < n; j++){
                if(i != j) {
                    adiac[i][n + j] = 1;
                    adiac[n + j][i] = 0;
                }
            }
        }
    }
    int edmond_karp(){
        parent.resize(nr_noduri, -1);
        parent[s] = s;
        bool still_running = true;
        int total_flux = 0;
        while(still_running){
            still_running = false;
            int curent_flux = bfs(s);
            if(curent_flux > 0){
                still_running = true;
                total_flux += curent_flux;
            }
        }
        return total_flux;
    }
    int bfs(int index){
        vector<bool> visited(nr_noduri, false);
        deque<pair<int, int>>coada; // nodul si fluxul cu care s-a ajuns in nod
        coada.push_front({index, infinity});
        visited[index] = true;
        while(!coada.empty()) {
            int nod = coada.front().first;
            int flux = coada.front().second;
            coada.pop_front();
            for (auto &vec: adiac[nod]) {
                if (!visited[vec.first] && vec.second > 0) {
                    parent[vec.first] = nod;
                    if(vec.first == t) {
                        flux = min(flux, vec.second);
                        rebalance(t, min(flux, vec.second));
                        return flux;
                    }
                    else{
                        visited[vec.first] = true;
                        if(vec.first < n)
                            coada.push_back({vec.first, min(flux, vec.second)});
                        else
                            coada.push_front({vec.first, min(flux, vec.second)});
                    }
                }
            }
        }
        return 0;
    }
    void rebalance(int index, int used_flux){
        while(index != parent[index]){
            adiac[parent[index]][index] -= used_flux;
            adiac[index][parent[index]] += used_flux;
            index = parent[index];
        }
    }
    void used_edges(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++)
                if(i != j && adiac[i][j + n] == 0)
                    g << i + 1 << ' ' << j + 1 << '\n';
        }
    }
};
int main() {
    Graph graf;
    g << graf.edmond_karp() << '\n';
    graf.used_edges();
    return 0;
}