匈牙利算法详解：二分图最大匹配及其应用

本文主要介绍了KM算法中的关键概念以及在二分图匹配问题上的应用。二分图（Bi-partite graph）是一种特殊的图，其中顶点被分为两个互不相邻的集合X和Y，所有边连接的顶点一个来自X，另一个来自Y。文章首先定义了可行顶标，它是图中每个顶点的值函数，满足对于图中任意一条边(x, y)，其顶标之和L(x) + L(y)应大于等于该边的权重w(x, y)。 在二分图中，一个匹配是指图中的一组边，这些边两两不共享任何顶点。最大匹配是指图中包含边数最多的匹配，它可能是完美匹配，即所有顶点都被匹配到。对于二分图的最大匹配问题，一个常见的解决方法是使用匈牙利算法，这是一种著名的优化算法，其时间复杂度为O(nm)，其中n是顶点数，m是边数。 匈牙利算法的核心思想是通过宽度优先搜索（类似于floodfill算法）来查找增广路径，即在图中添加边以增加匹配的数量，直到无法再添加为止。在这个过程中，算法会将图转化为一个简单的单位容量网络流问题，通过在二分图的两边添加源点s和汇点t，形成新的图结构，使得饱和的边在原图中对应于匹配的边。 举例来说，问题PKU1469是一个实际应用，它要求确定一个学生群体能否代表所有课程，每个学生只能选择一门课程。这个问题可以通过构建二分图并寻找最大匹配来解决。如果找到的最大匹配的大小至少等于课程数量，那么满足条件，输出"Yes"，否则输出"No"。 总结起来，本文讲解了二分图的基本概念、匹配的定义以及如何利用匈牙利算法求解最大匹配，这对于理解和解决实际问题中的二分图匹配问题非常有帮助。通过理解这些概念，读者可以掌握在IT领域中有效处理这类问题的关键技术。