Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Code for duality in CP article
Code snippets the article about linear programming duality.
#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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment