二分图的完美匹配 KM算法.docx

二分图的完美匹配是指在一个图中，每个顶点恰好被一条边连接，使得图中的所有顶点都被连接且没有多余未使用的边。在实际应用中，二分图的完美匹配常常出现在分配问题、调度问题等领域。KM算法，即Kuhn-Munkres算法，是一种求解二分图完美匹配的有效方法，具有较高的效率。 KM算法的核心思想是通过构建一个对偶图，并寻找增广路径来逐步完善匹配。以下是对KM算法的详细步骤： 1. 初始化：将所有边的权重设为无穷大（表示无边），然后用给定的边权重更新这些值。创建两个数组`xl`和`yl`，分别表示左部和右部顶点的最小期望值。再初始化一个匹配数组`match`，用于记录当前的匹配情况，以及两个辅助数组`xhash`和`yhash`，用于标记顶点状态。 2. 寻找增广路径：通过深度优先搜索（DFS）从未匹配的左部顶点开始，寻找一条可以通过未匹配或已匹配但可以改变的边到达未匹配的右部顶点的路径。如果找到这样的路径，更新匹配，并继续寻找新的增广路径。如果无法找到增广路径，说明当前的匹配已经是完美匹配。 3. 对偶调整：当无法找到增广路径时，更新对偶变量`xl`和`yl`，使得新的匹配可以找到增广路径。这一步是KM算法的关键，通过不断调整使得未匹配的顶点能够通过增加其期望值找到新的匹配机会。 4. 重复步骤2和3，直到找到完美匹配或无法找到增广路径为止。 在给出的AC代码中，`dfs`函数实现了寻找增广路径的过程，`KM_Perfect_Match`函数是整个算法的主体，其中包含对偶调整和寻找增广路径的循环。`Scanf`函数用于读入图的信息，`show`函数用于输出当前的匹配和边的情况，便于调试。 KM算法的时间复杂度是O(m^3)，其中m是图中边的数量，这是因为对偶调整的复杂度是O(m^2)，而寻找增广路径的DFS操作在最坏情况下需要O(m)时间。相比朴素的n^4算法，KM算法在处理大规模问题时具有显著的优势。 在给定的题目链接中，例如http://acm.hdu.edu.cn/showproblem.php?pid=1533，这些题目都是关于二分图完美匹配的应用实例，通过KM算法可以高效地找到解决方案。理解并掌握KM算法对于解决这类问题至关重要。