形式陈述

匈牙利算法求二分图完美匹配的最小总代价，等价于方阵指派问题。线性规划对偶为给左右顶点势 $u_i,v_j$，满足 $u_i+v_j\le c_{ij}$，最大化 $\sum u_i+\sum v_j$。算法维护对偶可行势和只含紧边 $u_i+v_j=c_{ij}$ 的相等子图，在其中寻找增广路；若无法增广，就按最小松弛量调整势以产生新紧边。经典实现为 $O(n^3)$。最大权版本可变号或改写势不等式。

直觉

势函数给每个任务和工人分摊一个“基础价格”。只有成本恰好等于两端价格和的边才可能进入当前最优结构；调价逐步暴露新的候选边。

例子与边界

三名工人与三项任务构成 $3\times 3$ 成本矩阵，算法最终选每行每列恰一个元素。矩形矩阵可补虚拟顶点和零/适当成本化为方阵。匈牙利算法求的是带权二分匹配，不是一般图带权匹配；也不能简单用逐行最便宜任务，因为会产生列冲突。势更新必须保持所有对偶约束可行，紧边上的完美匹配与对偶目标相等时由强对偶证明最优。

推论与应用

指派问题出现在任务调度、数据关联、最优配对和多目标跟踪；匈牙利算法也是原始—对偶方法的经典实例。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。