---
title: "The Hungarian Algorithm"
summary: Weighted assignment in O(n^3) with labels and equality subgraphs — the min-cost flow specialisation that is shorter, faster, and needs no graph.
difficulty: hard
tags: [matching, weights, dp]
time: n^3
space: n^2
prereq: [matching/bipartite, flow/mcmf]
see: [flow/mcmf, matching/applications]
---

## The assignment problem

:::definition label="Assignment"
Given an $n \times n$ cost matrix $A$, choose a permutation $\pi$ minimising $\sum_i A[i][\pi(i)]$. (Maximise a benefit? Negate, or use labels with the opposite sign.)
:::

## Labels, slack and the equality subgraph

:::props title="The duality that makes it work"
Keep **labels** $u_i$ (left) and $v_j$ (right) with the invariant $u_i + v_j \le 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 $\sum_i A[i][\pi(i)] = \sum_i (u_i + v_{\pi(i)}) = \sum u + \sum 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

```cpp hungarian.cpp
// 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]
```

:::note title="Read the code as the duality, not as magic"
`cur` = the slack $A[i_0][j] - u_{i_0} - v_j \ge 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 $\ge 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 $\le n$ iterations per row and $O(n^2)$ work per row: $O(n^3)$.
:::

## Correctness

:::theorem title="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.
:::

:::proof
Feasibility: for $j$ not in the tree, $u$ is unchanged for its row's... formally, `minv[j] -= delta` is exactly $A[i][j] - u_i - v_j \ge \operatorname{slack} - \delta \ge 0$ for the tree row $i$ that achieved `minv[j]`, and other rows only become "more slack" since their $u$ increases by $\delta$ at most as much; for $j$ in the tree, $v_j$ decreases by $\delta$ while $u_{p[j]}$ increases by $\delta$, so the sum $u+v$ is unchanged and equality edges stay tight. Optimality is the bound above: any permutation costs $\ge \sum u + \sum v$, and the produced one attains it (all its edges are tight). ∎
:::

## Hungarian vs min-cost max-flow

:::props title="Hungarian vs. min-cost max-flow on the same instance"
| | Hungarian | MCMF (potentials + Dijkstra) |
|---|---|---|
| setup | $O(n^2)$ matrix, no graph | build $2n + 2$ nodes, $n^2$ edges |
| time | $O(n^3)$ always | $O(n^2 \cdot n \log n) = O(n^3 \log n)$, similar constant |
| rectangular $k \times n$, $k \le n$ | pad with zero rows, same code | free |
| extra constraints (forbidden pairs, capacity on a side) | awkward | natural |
| memory | $O(n^2)$ for $A$ | $O(n^2)$ for the edges — both die at $n \approx 5000$ |
| maximise with large weights | trivial | same |
:::

## Four details that decide WA vs AC

:::warning title="Four details that decide WA vs AC"
1. $u$ is indexed by **rows**, $v$ by **columns**, and the answer is $-v[0]$ — using $\sum A$ after the fact is safer than any identity,
2. for a **max** problem with non-negative weights, negate $A$; labels may then be negative, which is fine — but do *not* initialise `u`, `v` to $0$ when $A$ is huge and you use `int` (overflow in `cur`),
3. 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),
4. 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

:::example title="The variant people actually need: assignment with a forbidden set"
$A[i][j] = \infty$ for forbidden pairs works *only* if the labels can absorb it; use a large but finite value (say $10^{12}$) 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 $u_i = \min_j A[i][j]$; the loop handles it, but a hand-written "labels = 0" initialisation does not.
:::

:::problems
- [[CSES 2121]] Parcel Delivery | https://cses.fi/problemset/task/2121 | hard | flow-with-costs — the case where MCMF is the right tool and Hungarian is not
- [[CSES 1631]] Reading Books | https://cses.fi/problemset/task/1631 | easy | a "pairing" instance with no matching needed — a good calibration of when not to reach for the algorithm
:::