Kuhn-Munkres算法（二分图最大权匹配） 题目描述 给定一个完全二分图 \( G = (X \cup Y, E) \)，其中 \( |X| = |Y| = n \)，每条边 \( (x_ i, y_ j) \) 有一个权重 \( w_ {ij} \geq 0 \)。要求找到一种完美匹配（所有顶点均被匹配），使得匹配边的权重之和最大。 解题过程 问题转换 若需解决最小权匹配，可将权重取负后转化为最大权匹配。 算法通过维护顶标（label）函数 \( l(x) \) 和 \( l(y) \) 来构造等价子图，并在其中寻找完美匹配。 初始化顶标与等价子图 初始化顶标： \[ \forall x \in X,\ l(x) = \max_ {y \in Y} w(x,y); \quad \forall y \in Y,\ l(y) = 0 \] 构建等价子图 \( G_ l \)：包含所有满足 \( l(x) + l(y) = w(x,y) \) 的边 \( (x,y) \)。 尝试在等价子图中找完美匹配 使用匈牙利算法（DFS或BFS）在 \( G_ l \) 中寻找完美匹配。 若找到，算法结束，当前匹配即为最大权匹配。 调整顶标以扩展等价子图 若未找到完美匹配，记： \( S \subseteq X \)：当前匹配中已访问的X集合顶点。 \( T \subseteq Y \)：当前匹配中已访问的Y集合顶点。 计算松弛量： \[ \alpha_ l = \min_ {x \in S, y \notin T} \{ l(x) + l(y) - w(x,y) \} \] 调整顶标以加入新边： \[ \forall x \in S,\ l(x) \leftarrow l(x) - \alpha_ l; \quad \forall y \in T,\ l(y) \leftarrow l(y) + \alpha_ l \] 调整后，等价子图 \( G_ l \) 会加入新边（可能包括连接未匹配点的边），同时保留原有匹配边。 重复过程 用新顶标重建等价子图，继续尝试寻找完美匹配，直到成功。 示例说明 假设二分图权重矩阵为： \[ \begin{bmatrix} 3 & 0 & 4 \\ 2 & 1 & 3 \\ 0 & 0 & 5 \\ \end{bmatrix} \] 初始化顶标：\( l(X) = [ 4, 3, 5] \), \( l(Y) = [ 0, 0, 0 ] \)。 等价子图包含边：\( (x_ 1,y_ 3), (x_ 2,y_ 3), (x_ 3,y_ 3) \)。 通过多次顶标调整（如减少 \( l(x_ 1) \) 以加入边 \( (x_ 1,y_ 1) \)），逐步扩展等价子图，最终找到权重和为 \( 3+3+5=11 \) 的完美匹配。 关键点 顶标调整保证等价子图始终包含当前匹配，同时逐步加入新边。 时间复杂度为 \( O(n^3) \)，适用于稠密二分图的最大权匹配问题。