二分图的最大权匹配（Kuhn-Munkres算法） 题目描述 给定一个完全二分图 \( G = (X \cup Y, E) \)，其中 \( |X| = |Y| = n \)，每条边 \( (i, j) \) 有一个权重 \( w(i, j) \geq 0 \)。要求找到一种完美匹配（即每个顶点恰好匹配一次），使得匹配边的权重之和最大。 解题步骤 问题转换 若需解决最小权匹配，可将权重取负后转为最大权匹配。 算法通过维护顶点标号（顶标）和等价子图来逐步优化匹配。 初始化 定义顶标函数 \( l(x) \)（左部点）和 \( l(y) \)（右部点），满足 \( l(x) + l(y) \geq w(x, y) \)。 初始顶标：左部点 \( l(x_ i) = \max_ {j} w(x_ i, y_ j) \)，右部点 \( l(y_ j) = 0 \)。 构建等价子图 \( G_ l \)：仅保留满足 \( l(x) + l(y) = w(x, y) \) 的边。 寻找匹配 在等价子图 \( G_ l \) 中使用匈牙利算法（DFS或BFS）寻找完美匹配。 若找到完美匹配，算法结束，当前匹配即为最大权匹配。 调整顶标 若未找到完美匹配，记 \( S \subseteq X \) 为已访问的左部点，\( T \subseteq Y \) 为已访问的右部点。 计算调整量 \( \delta = \min\{l(x) + l(y) - w(x, y) \mid x \in S, y \notin T\} \)。 更新顶标： \( l(x) \leftarrow l(x) - \delta \)（若 \( x \in S \)） \( l(y) \leftarrow l(y) + \delta \)（若 \( y \in T \)） 调整后等价子图 \( G_ l \) 会加入新边（如连接 \( S \) 和 \( Y \setminus T \) 的边），同时保持已匹配边仍在子图中。 迭代优化 重复步骤3-4，直至找到完美匹配。每次顶标调整均使等价子图扩张，最终必能找到最优解。 关键点 顶标不等式 \( l(x) + l(y) \geq w(x, y) \) 保证了解的最优性。 调整量 \( \delta \) 确保至少一条新边加入等价子图，逐步逼近完美匹配。 时间复杂度为 \( O(n^3) \)，适用于稠密二分图。