Chapter 13 · Matching
The Hungarian Algorithm
Weighted assignment in O(n^3) with labels and equality subgraphs — the min-cost flow specialisation that is shorter, faster, and needs no graph.
#The assignment problem
Given an n × n cost matrix A, choose a permutation π minimising ∑i A[i][π(i)]. (Maximise a benefit? Negate, or use labels with the opposite sign.)
#Labels, slack and the equality subgraph
The duality that makes it work
Keep labels ui (left) and vj (right) with the invariant ui + vj ≤ A[i][j] (feasible). The equality subgraph has the edges where equality holds. Then:
- any matching M in the equality subgraph with |M| = n is optimal, because ∑i A[i][π(i)] = ∑i (ui + vπ(i)) = ∑ u + ∑ v, which is a lower bound for every permutation;
- so the algorithm alternates two moves: augment inside the equality subgraph, and when it cannot, adjust labels to add exactly one new edge while keeping feasibility.
#Implementation
// A is 1-indexed, n x n. Returns the min cost and p[] = assignment (p[j] = row matched to column j).
vector<long long> u(n + 1), v(n + 1);
vector<int> p(n + 1), way(n + 1);
for (int i = 1; i <= n; i++) {
p[0] = i;
int j0 = 0;
vector<long long> minv(n + 1, INF);
vector<char> used(n + 1, false);
do {
used[j0] = true;
int i0 = p[j0], j1 = -1;
long long delta = INF;
for (int j = 1; j <= n; j++) if (!used[j]) {
long long cur = A[i0][j] - u[i0] - v[j];
if (cur < minv[j]) { minv[j] = cur; way[j] = j0; }
if (minv[j] < delta) { delta = minv[j]; j1 = j; }
}
for (int j = 0; j <= n; j++) {
if (used[j]) { u[p[j]] += delta; v[j] -= delta; }
else minv[j] -= delta;
}
j0 = j1;
} while (p[j0]);
do { // augment along `way`
int j1 = way[j0]; p[j0] = p[j1]; j0 = j1;
} while (j0);
}
// cost = -v[0] (or sum A[p[j]][j]); assignment: column j gets row p[j]cur = the slack A[i0][j] - ui0 - vj ≥ 0; minv[j] is the minimum slack to reach column j from the alternating tree built so far; delta is the minimum of minv over the unvisited columns, exactly the largest label shift that keeps every reduced cost ≥ 0 while making one new edge tight. After the shift, the columns with minv[j] == delta join the equality subgraph, i.e. the tree grows by at least one vertex each iteration — hence ≤ n iterations per row and O(n2) work per row: O(n3).
#Correctness
At the end, p is a perfect matching in the equality subgraph of feasible labels, therefore optimal; and the labels are always feasible because every shift subtracts the minimum slack.
Feasibility: for j not in the tree, u is unchanged for its row's... formally, minv[j] -= delta is exactly A[i][j] - ui - vj ≥ slack - δ ≥ 0 for the tree row i that achieved minv[j], and other rows only become "more slack" since their u increases by δ at most as much; for j in the tree, vj decreases by δ while up[j] increases by δ, so the sum u+v is unchanged and equality edges stay tight. Optimality is the bound above: any permutation costs ≥ ∑ u + ∑ v, and the produced one attains it (all its edges are tight). ∎
#Hungarian vs min-cost max-flow
Hungarian vs. min-cost max-flow on the same instance
| Hungarian | MCMF (potentials + Dijkstra) | |
|---|---|---|
| setup | O(n2) matrix, no graph | build 2n + 2 nodes, n2 edges |
| time | O(n3) always | O(n2 · n log n) = O(n3 log n), similar constant |
| rectangular k × n, k ≤ n | pad with zero rows, same code | free |
| extra constraints (forbidden pairs, capacity on a side) | awkward | natural |
| memory | O(n2) for A | O(n2) for the edges — both die at n ≈ 5000 |
| maximise with large weights | trivial | same |
#Four details that decide WA vs AC
- u is indexed by rows, v by columns, and the answer is -v[0] — using ∑ A after the fact is safer than any identity,
- for a max problem with non-negative weights, negate A; labels may then be negative, which is fine — but do not initialise
u,vto 0 when A is huge and you useint(overflow incur), - rectangular instances need padding to square (rows = min side), and reading
p[j]beyond the padded rows silently returns 0 (which the code uses as its null column), - if the problem allows not assigning some rows for a cost, that is an assignment with an extra "dummy column" per row — the dummy's cost is the penalty; forgetting the dummy is the classic "negative answers" bug.
#Variants
A[i][j] = ∞ for forbidden pairs works only if the labels can absorb it; use a large but finite value (say 1012) rather than INF, otherwise cur = INF - u - v overflows and the "delta" step adds infinity to every label, producing an answer of nan-like garbage. Feasibility of the initial labels is also required: if all A[i][*] are huge for one row, start with ui = minj A[i][j]; the loop handles it, but a hand-written "labels = 0" initialisation does not.