Skip to content

Hungarian Hot Sheet

Use this sheet when the statement is really one square weighted assignment and you want the shortest route back to O(n^3) Hungarian.

Do Not Use When

  • the objective is only cardinality -> Matching hot sheet
  • capacities, sparse feasibility edges, or extra routing structure dominate -> Min-Cost Flow hot sheet
  • the graph is not bipartite
  • the problem is still fuzzy enough that you cannot state "one row, one column, minimum total cost"

Choose By Signal

  • dense n x n cost matrix + exact one-to-one assignment -> Hungarian / Assignment Problem
  • sparse or capacity-rich costed assignment model -> Min-Cost Flow hot sheet
  • plain bipartite pairing with no weights -> Matching hot sheet

Core Invariants

  • dual potentials satisfy u[i] + v[j] <= cost[i][j]
  • reduced slack cost[i][j] - u[i] - v[j] stays nonnegative
  • only zero-slack edges are tight enough to join the current equality matching
  • each augmentation increases the number of assigned rows by exactly 1

Main Traps

  • using Hungarian when the graph is really sparse and min-cost flow is the clearer mental model
  • forgetting the repo starter is intentionally square-matrix first
  • mixing row/column indexing when reconstructing the assignment
  • negating weights for max-assignment without upgrading to long long

Exact Starter Route

Reopen Paths