Cod sursa(job #3181340)

Utilizator DRGmenMarcu Dragos-Ionut DRGmen Data 6 decembrie 2023 21:05:57
Problema Taramul Nicaieri Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.47 kb
#include <bits/stdc++.h>

using namespace std;

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

bool vect_comp(vector<int> &a, vector<int> &b) {
    return a[2] < b[2];
}

class Graf {
    vector<unordered_set<int>> muchii;
    map<pair<int, int>, int> val_muchii;
    int nr_noduri;
    vector<int> dsu;
    int dsu_default;
    vector<int> dsu_size;
public:

    Graf(int n) : nr_noduri(n) {
        innit_dsu(n + 1, -1);
        muchii.assign(n + 1, unordered_set<int>());
    }

    void add_muchie(int x, int y, int cost = 0) {
        muchii[x].insert(y);
        val_muchii[{x, y}] = cost;
    }

    void stergere_muchie(int x, int y) {
        muchii[x].erase(y);
    }

    void innit_dsu(int n, int _default) {
        dsu.assign(n + 1, _default);
        dsu_default = _default;
        dsu_size.assign(n + 1, 1);
    }

    int get_dsu_size(int n) {
        return dsu_size[find_parent(n)];
    }

    void make_dsu(int nod) {
        dsu[nod] = nod;
        dsu_size[nod] = 1;
    }

    int find_parent(int nod) {
        if (dsu[nod] == dsu_default) return dsu_default;
        if (nod == dsu[nod]) return nod;
        return dsu[nod] = find_parent(dsu[nod]);
    }

    void union_sets(int s1, int s2) {
        s1 = find_parent(s1);
        s2 = find_parent(s2);
        if (s1 != s2) {
            if (dsu_size[s1] < dsu_size[s2]) swap(s1, s2);
            dsu[s2] = s1;
            dsu_size[s1] += dsu_size[s2];
        }
    }

    int make_apm(vector<vector<int>> &v_muchii) { // se considera sortate
        for (int i = 0; i <= nr_noduri; i++) {
            make_dsu(i);
        }
        int sum_apm = 0;
        for (auto &it: v_muchii) {
            int x = it[0], y = it[1], cost = it[2];
            if (find_parent(x) != find_parent(y)) {
                add_muchie(x, y, cost);
                add_muchie(y, x, cost);
                union_sets(x, y);
                sum_apm += cost;
            }
        }
        return sum_apm;
    }

    int bfs_maxflow(int n1, int n2, vector<int> &parents) {
        queue<pair<int, int>> q;
        q.push({n1, INT_MAX});
        parents[n1] = n1;
        while (!q.empty()) {
            int nod = q.front().first;
            int cap_c = q.front().second;
            q.pop();
            for (auto &vecin: muchii[nod]) {
                int r_cap = val_muchii[{nod, vecin}];
                if (r_cap > 0 && parents[vecin] == -1) {
                    parents[vecin] = nod;
                    if (vecin == n2) return min(cap_c, r_cap);
                    q.push({vecin, min(cap_c, r_cap)});
                }
            }
        }
        return 0;
    }

    int dfs_maxflow(int nodc, int cost_min, int n2, vector<int> &parents){
        for(auto &vecin: muchii[nodc]){
            if(parents[vecin] == -1 && val_muchii[{nodc, vecin}] > 0){
                parents[vecin] = nodc;
                if(vecin == n2) {
                    return min(cost_min, val_muchii[{nodc, vecin}]);
                }
                int ret = dfs_maxflow(vecin, min(cost_min, val_muchii[{nodc, vecin}]), n2, parents);
                if(ret == 0){
                    parents[vecin] = -1;
                }
                else{
                    return ret;
                }
            }
        }
        return 0;
    }

    void maxflow(int n1, int n2, int n) {
        int cap_min = 0;
        vector<int> p(n2 + 1, -1);
        while ((cap_min = dfs_maxflow(n1, 1000, n2, p))) {
            p[n1] = n1;
            int nodc = n2;
            while (nodc != n1) {
                val_muchii[{p[nodc], nodc}] -= cap_min;
                val_muchii[{nodc, p[nodc]}] += cap_min;
                nodc = p[nodc];
            }
            p.assign(n2 + 1, -1);
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i != j && val_muchii[{i, n+j}] == 0){
                    fout << i  << ' ' << j << '\n';
                }
            }
        }
    }

};

int main() {
    std::cin.sync_with_stdio(0);
    cin.tie(0);
    int n, nr_muchii = 0;
    fin >> n;
    Graf g(2 * n + 1);
    for (int i = 1; i <= n; i++) {
        int iesiri, intrari;
        fin >> iesiri >> intrari;
        nr_muchii += iesiri;
        g.add_muchie(0, i, iesiri);
        g.add_muchie(n+i, 2 * n + 1, intrari);
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                g.add_muchie(i, n + j, 1);
                g.add_muchie(n + j, i, 0);
            }
        }
    }
    fout << nr_muchii << '\n';
    g.maxflow(0, 2 * n + 1, n);
    return 0;
}