Chapter 12 · Cuts and Flows
Min-Cost Max-Flow
Successive shortest augmenting paths with potentials, why negative cycles cannot appear, and the assignment/transportation problems it solves.
#The problem, and augmenting along cheapest paths
Capacities c(e) and per-unit costs a(e). Among all flows of maximum value (or of a given value F), minimise ∑e a(e) f(e).
Start with f = 0. Repeatedly find a shortest (cheapest) s ⇝ t path in the residual graph w.r.t. reduced costs, and augment along it. If costs are non-negative, the flow of value k produced after k augmentations (unit capacities) — and in general after each augmentation — is a minimum-cost flow of that value.
The residual graph of an optimal flow of value v contains no negative cycle: a negative cycle C could be augmented (it preserves conservation at every vertex) to strictly improve the cost — contradiction. Conversely, if f is min-cost for its value and P is a cheapest s ⇝ t residual path, then f + δ P is min-cost for value |f| + δ: any other flow g of that value differs from f by a decomposition into residual s ⇝ t paths and cycles, whose costs are ≥ c(P) (paths) and ≥ 0 (cycles, by optimality of f), so cost(g) - cost(f) ≥ (amount) · c(P) = cost(f + δ P) - cost(f). ∎
#Implementation with potentials
struct Edge { int to, rev, cap; long long cost; };
vector<vector<Edge>> g(n);
void add(int u, int v, int cap, long long cost) {
g[u].push_back({v, (int)g[v].size(), cap, cost});
g[v].push_back({u, (int)g[u].size() - 1, 0, -cost});
}
const long long INF = 4e18;
long long pot[n]; // potentials = shortest distances so far
priority_queue<pair<long long,int>, vector<...>, greater<...>> pq;
while (need) {
// Dijkstra on reduced costs a(u,v) + pot[u] - pot[v] >= 0
fill(dist, dist + n, INF); dist[s] = 0; pq.push({0, s});
while (pq.size()) { auto [d,v] = pq.top(); pq.pop(); if (d > dist[v]) continue;
for (auto &e : g[v]) if (e.cap && dist[e.to] > dist[v] + e.cost + pot[v] - pot[e.to]) {
dist[e.to] = dist[v] + e.cost + pot[v] - pot[e.to]; pv[e.to] = v; pe[e.to] = &e; pq.push({dist[e.to], e.to});
} }
if (dist[t] == INF) break; // no more augmenting paths -> flow is maximum
for (int v = 0; v < n; v++) if (dist[v] < INF) pot[v] += dist[v];
int add = need; // bottleneck along the path
for (int v = t; v != s; v = pv[v]) add = min(add, g[pv[v]][pe[v]].cap);
for (int v = t; v != s; v = pv[v]) {
Edge &e = g[pv[v]][pe[v]];
e.cap -= add; g[v][e.rev].cap += add;
}
flow += add; cost += add * pot[t]; // pot[t] is the true shortest distance s->t
need -= add;
}#Why potentials work
Reduced cost a'(u,v) = a(u,v) + p(u) - p(v) preserves the cost of every s ⇝ t path up to the constant p(s) - p(t) (internal vertices cancel), and every cycle cost exactly. Choosing p = the shortest-distance vector from the previous round makes all residual edges non-negative: for an edge with residual capacity, d(v) ≤ d(u) + a(u,v), i.e. a'(u,v) ≥ 0. So Dijkstra is applicable, and after updating p += d the invariant is maintained. This is the same re-weighting trick as Johnson's algorithm (Bellman–Ford and Negative Weights's re-weighting remark), and it is the reason the O(VE) Bellman–Ford per round becomes O(E log V).
#Negative cycles and overflow
Residual edges carry negative costs (-a(e)), so the graph always has negative edges; potentials are what remove them. Three consequences:
- the first round needs Bellman–Ford (or SPFA) to get valid potentials if any original cost is negative — with non-negative costs, p = 0 works;
- vertices unreachable in a round must keep their old potential (never "reset to 0"), or reduced costs go negative and Dijkstra silently returns a wrong path;
- cost overflow: with |a| ≤ 106, F ≤ 106 units, the total is 1012 —
long longthroughout, andINF = 4e18(not1e18 + 1e18overflow in the relaxation test).
#Complexity, honestly stated
Complexity, honestly stated
- O(F · E log V) with unit capacities (one unit per augmentation),
- O(VE · min(V2/3, √E) log V)-ish for unit networks (bipartite matching: E√V phases if you augment a blocking flow per distance — the Hopcroft–Karp speed-up, Hopcroft–Karp),
- strongly polynomial algorithms exist (Tardos; Orlin's O(V^2E)log V) but nobody implements them;
- cost scaling / capacity scaling variants are what fast libraries (LEMON, AtCoder
mcf_graph) do: slope-based, with aslope()API returning the piecewise-linear cost-vs-flow curve for free — the same curve you would otherwise compute by hand by reading the augmentation sequence.
#Modelling: transportation and assignment
- Assignment: s → worker (cap 1), worker → job (cap 1, cost = price), job → t (cap 1). Min-cost max-flow of value n = the optimal assignment; the Hungarian algorithm (The Hungarian Algorithm) is the same computation specialised, in O(n3) and without a graph.
- Transportation with supplies oi and demands dj: same network with capacities oi, dj; feasibility = max flow saturates all supply edges (this is the max-flow-with-demands check, Max Flow: Ford–Fulkerson, Dinic, Push–Relabel).
- "Send K units, each path costs its length" — CSES Parcel Delivery: capacities on roads, unit cost per road, ask for cost of sending K. MCMF with F = K is exactly intended when K ≤ 100, n ≤ 500.
- Min-cost circulation with lower bounds: satisfy ℓ(e) ≤ f(e) ≤ c(e) by pre-sending ℓ(e), correcting imbalances with a super source/sink — the standard O(V+E)-line reduction that turns "flow with demands" into plain MCMF.
#When not to use MCMF
- Only the value matters ⇒ plain max flow (faster by 10–50×),
- costs on vertices only and you need min-cost paths (not flows) ⇒ DP/Dijkstra per query,
- assignment with n ≤ 500 ⇒ Hungarian is simpler and 5× faster than generic MCMF,
- convex costs ⇒ split an edge into ⌈log c⌉ parallel edges with costs a, 2a, 4a, … (or unit-cost bundles), which keeps the graph a DAG-ish shape and the flow integral.