二分图的最大权匹配（Kuhn-Munkres算法） 题目描述 给定一个完全二分图 \( G = (X \cup Y, E) \)，其中 \( |X| = |Y| = n \)，每条边 \( (x_ i, y_ j) \) 有一个权重 \( w_ {ij} \geq 0 \)。要求找到一种完美匹配（即每个顶点恰好匹配一次），使得匹配边的权重之和最大。 解题过程 Kuhn-Munkres算法（又称匈牙利算法）通过顶点标号（顶标）和等价子图构造，逐步调整标号以找到最大权匹配。以下是详细步骤： 初始化顶标与等价子图 定义顶点标号函数 \( l(x) \) 和 \( l(y) \)，初始时对 \( X \) 中点设置 \( l(x_ i) = \max_ {j} w_ {ij} \)，对 \( Y \) 中点设置 \( l(y_ j) = 0 \)。 构建等价子图 \( G_ l \)：包含所有满足 \( l(x_ i) + l(y_ j) = w_ {ij} \) 的边 \( (x_ i, y_ j) \)。 在等价子图中寻找完美匹配 使用DFS或BFS在 \( G_ l \) 中寻找完美匹配（例如用匈牙利算法求最大基数匹配）。 若找到完美匹配，算法结束，此匹配即为最大权匹配。 若未找到，记当前匹配为 \( M \)，需调整顶标以扩展等价子图。 调整顶标以扩展等价子图 从 \( X \) 中未匹配点出发，标记所有通过交错路径（交替经过匹配边和非匹配边）可达的点，得到集合 \( S \subseteq X \) 和 \( T \subseteq Y \)。 计算调整量 \( \delta = \min\{ l(x_ i) + l(y_ j) - w_ {ij} \mid x_ i \in S, y_ j \notin T \} \)。 调整顶标： 对 \( x_ i \in S \)，执行 \( l(x_ i) \leftarrow l(x_ i) - \delta \)； 对 \( y_ j \in T \)，执行 \( l(y_ j) \leftarrow l(y_ j) + \delta \)； 其他顶点标号不变。 调整后，等价子图 \( G_ l \) 会加入新边（例如连接 \( S \) 和 \( Y \setminus T \) 的边），但保留原有匹配边。 迭代直至找到完美匹配 重复步骤2和3，直到在等价子图中找到完美匹配。每次顶标调整保证至少有一条新边加入等价子图，确保算法在 \( O(n^3) \) 时间内收敛。 关键点说明 顶标性质：始终满足 \( l(x_ i) + l(y_ j) \geq w_ {ij} \)，确保最终匹配的权重和等于顶标和的上界。 复杂度：通过DFS寻找增广路和顶标调整，总复杂度为 \( O(n^3) \)。 通过以上步骤，算法逐步逼近最优解，最终在等价子图中找到最大权完美匹配。