Code for duality in CP article

#Duality in LP

Code snippets the article about linear programming duality.

inverse_MST.cpp

#include <bits/stdc++.h>

using namespace std;

struct network {
    int n;
    vector<int> to, cost, cap, dist;
    vector<vector<int>> g;
    
    network(int n): n(n), dist(n), g(n) {}
    
    void add_edge(int a, int b, int cst, int cp) {
        g[a].push_back(to.size());
        to.push_back(b);
        cap.push_back(cp);
        cost.push_back(cst);
    }
    
    void add(int a, int b, int cst, int cp = 1) {
        add_edge(a, b, cst, cp);
        add_edge(b, a, -cst, 0);
    }
    
    void mincost() {
        do {
            vector<int> in_que(n), par(n);
            deque<int> que = {0};
            dist.assign(n, 1e9);
            dist[0] = 0;
            while(!que.empty()) { // SPFA
                int v = que.front();
                in_que[v] = 0;
                que.pop_front();
                for(auto it: g[v]) {
                    if(cap[it]) {
                        auto [u, c] = tie(to[it], cost[it]);
                        if(dist[v] + c < dist[u]) {
                            dist[u] = dist[v] + c;
                            par[u] = it;
                            if(!in_que[u]) {
                                que.push_back(u);
                                in_que[u] = true;
                            }
                        }
                    }
                }
            }
            if(dist[1] < 0) { // 1 unit of flow per time
                int t = 1;
                while(t) {
                    auto it = par[t];
                    cap[it]--;
                    cap[it ^ 1]++;
                    t = to[it ^ 1];
                }
            }
        } while(dist[1] < 0);
    }
};

struct bipartite {
    int n, m;
    network nt;
    
    bipartite(int n, int m): n(n), m(m), nt(n + m + 2) {
        for(int i = 0; i < n; i++) {
            nt.add(0, i + 2, 0);
        }
        for(int j = 0; j < m; j++) {
            nt.add(j + n + 2, 1, 0);
        }
    }
    
    void add(int a, int b, int c) {
        nt.add(a + 2, b + n + 2, c, 1e9);
    }
    
    pair<vector<int>, vector<int>> potentials() {
        nt.add(0, 1, 0);
        nt.mincost();
        vector<int> pts[2];
        for(int i = 0; i < n; i++) {
            pts[0].push_back(-nt.dist[i + 2]);
        }
        for(int j = 0; j < m; j++) {
            pts[1].push_back(-nt.dist[j + n + 2]);
        }
        return make_pair(pts[0], pts[1]);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    bipartite me(n - 1, m - (n - 1));
    int u[m], v[m], c[m];
    vector<pair<int, int>> g[n];
    for(int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> c[i];
        u[i]--, v[i]--;
        if(i < n - 1) {
            g[u[i]].emplace_back(i, v[i]);
            g[v[i]].emplace_back(i, u[i]);
        } else {
            vector<int> P;
            function<bool(int, int, int)> dfs = [&](int v, int p, int t) {
                if(v == t) {
                    return true;
                }
                for(auto [e, u]: g[v]) {
                    if(u != p) {
                        P.push_back(e);
                        if(dfs(u, v, t)) {
                            return true;
                        } else {
                            P.pop_back();
                        }
                    }
                }
                return false;
            };
            dfs(u[i], u[i], v[i]);
            for(auto jt: P) {
                me.add(jt, i - (n - 1), c[i] - c[jt]);
            }
        }
    }
    
    auto [A, B] = me.potentials();
    for(int i = 0; i < m; i++) {
        if(i < n - 1) {
            c[i] += min(0, A[i]);
        } else {
            c[i] += max(0, B[i - (n - 1)]);
        }
        cout << c[i] << "\n";
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;// cin >> t;
    while(t--) {
        solve();
    }
}