---
title: "Min-Cost Max-Flow"
summary: Successive shortest augmenting paths with potentials, why negative cycles cannot appear, and the assignment/transportation problems it solves.
difficulty: hard
tags: [flow, costs, matching]
time: F * E log V typical
prereq: [flow/maxflow, shortest/dijkstra]
see: [matching/hungarian, shortest/bellman-ford]
---

## The problem, and augmenting along cheapest paths

:::definition label="MCMF"
Capacities $c(e)$ **and** per-unit costs $a(e)$. Among all flows of maximum value (or of a given value $F$), minimise $\sum_e a(e) f(e)$.
:::

:::theorem title="Successive shortest paths"
Start with $f = 0$. Repeatedly find a **shortest** (cheapest) $s \leadsto 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.
:::

:::proof
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 \leadsto t$ residual path, then $f + \delta P$ is min-cost for value $|f| + \delta$: any other flow $g$ of that value differs from $f$ by a decomposition into residual $s \leadsto t$ paths and cycles, whose costs are $\ge c(P)$ (paths) and $\ge 0$ (cycles, by optimality of $f$), so $\operatorname{cost}(g) - \operatorname{cost}(f) \ge (\text{amount}) \cdot c(P) = \operatorname{cost}(f + \delta P) - \operatorname{cost}(f)$. ∎
:::

## Implementation with potentials

```cpp mcmf.cpp
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

:::note title="Why potentials, and why they stay valid"
Reduced cost $a'(u,v) = a(u,v) + p(u) - p(v)$ preserves the cost of every $s \leadsto 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) \le d(u) + a(u,v)$, i.e. $a'(u,v) \ge 0$. So Dijkstra is applicable, and after updating $p \mathrel{+}= d$ the invariant is maintained. This is the same re-weighting trick as Johnson's algorithm (@shortest/bellman-ford'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

:::warning title="The negative-cycle trap in a residual graph"
Residual edges carry **negative** costs ($-a(e)$), so the graph always has negative edges; potentials are what remove them. Three consequences:
1. 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;
2. 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;
3. **cost overflow**: with $|a| \le 10^6$, $F \le 10^6$ units, the total is $10^{12}$ — `long long` throughout, and `INF = 4e18` (not `1e18 + 1e18` overflow in the relaxation test).
:::

## Complexity, honestly stated

:::props title="Complexity, honestly stated"
- $O(F \cdot E \log V)$ with unit capacities (one unit per augmentation),
- $O(VE \cdot \min(V^{2/3}, \sqrt E) \log V)$-ish for **unit networks** (bipartite matching: $E\sqrt V$ phases if you augment a *blocking flow* per distance — the Hopcroft–Karp speed-up, @matching/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 a `slope()` 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

:::example title="Modelling: transportation and assignment"
- **Assignment**: $s \to$ worker (cap 1), worker $\to$ job (cap 1, cost = price), job $\to t$ (cap 1). Min-cost max-flow of value $n$ = the optimal assignment; the Hungarian algorithm (@matching/hungarian) is the same computation specialised, in $O(n^3)$ and without a graph.
- **Transportation** with supplies $o_i$ and demands $d_j$: same network with capacities $o_i, d_j$; feasibility = max flow saturates all supply edges (this is the max-flow-with-demands check, @flow/maxflow).
- **"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 \le 100$, $n \le 500$.
- **Min-cost circulation with lower bounds**: satisfy $\ell(e) \le f(e) \le c(e)$ by pre-sending $\ell(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

:::note title="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 \le 500$ ⇒ Hungarian is simpler and 5× faster than generic MCMF,
- convex costs ⇒ split an edge into $\lceil\log c\rceil$ parallel edges with costs $a, 2a, 4a, \dots$ (or unit-cost bundles), which keeps the graph a DAG-ish shape and the flow integral.
:::

:::problems
- [[CSES 2121]] Parcel Delivery | https://cses.fi/problemset/task/2121 | hard | exactly the K-unit min-cost flow statement
- [[CSES 1694]] Download Speed | https://cses.fi/problemset/task/1694 | easy | the same graph with no costs: plain max flow is 20x faster — know which one you need
:::