Cod sursa(job #3181356)

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

using namespace std;

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

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

    Graf(int n) : nr_noduri(n) {
        muchii.assign(n + 1, vector<int>());
        val_muchii.assign(n + 1, vector<int>(n+1, 0));
    }

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

    int bfs_maxflow(int n1, int n2, vector<int> &parents) {
        queue<pair<int, int>> q;
        q.push({n1, 1000});
        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;
    }

    void maxflow(int n1, int n2, int n) {
        int cap_min = 0;
        vector<int> p(n2 + 1, -1);
        while ((cap_min = bfs_maxflow(n1, n2, p))) {
            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;
}