Skip to content

Graphs -> Hungarian / Assignment Problem

Dense square weighted assignment via Hungarian's O(n^3) primal-dual algorithm, with direct recovery of one minimum-cost perfect matching.

  • Topic slug: graphs/hungarian-assignment
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 1
  • Repo companion pages: 5
  • Curated external problems: 3

Microtopics

  • assignment-matrix
  • weighted-bipartite-matching
  • potentials
  • reduced-slack
  • tight-edges
  • primal-dual

Learning Sources

Source Type
cp-algorithms Hungarian algorithm Reference
KACTL WeightedMatching / Hungarian Reference
OI Wiki weighted bipartite matching Reference

Practice Sources

Source Type
CSES Task Assignment Practice
SPOJ ASSIGN4 Practice
The Great Wall Game Practice

Repo Companion Material

Material Type
Hungarian hot sheet quick reference
Hungarian starter route starter route
Task Assignment note anchor note
Matching tutorial compare point
Min-Cost Flow tutorial compare point

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Task Assignment CSES Hard Weighted Matching Dense Cost Matrix; Weighted Bipartite Matching Bipartite Matching Basics; Minimum Total Cost Modeling Cost Matrix; Perfect Matching The cleanest square assignment benchmark with explicit witness output.

Practice

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Another Assignment Problem SPOJ Medium - Weighted Bipartite Matching; Assignment Matrix Assignment Matrix; Perfect Matching Weighted Matching; Optimization Direct costed assignment practice after the flagship matrix-first route.

Stretch

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
The Great Wall Game ACM regional archive Hard Geometry Geometry To Cost Matrix; Minimum Cost Perfect Matching Distance Cost Modeling; Hungarian Basics Manhattan Distance; Modeling A strong modeling extension where coordinates collapse cleanly into an assignment-cost matrix.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
TASKASSIGNMENT Task Assignment primary hard - Note Code

Regeneration

python3 scripts/generate_problem_catalog.py