匈牙利算法解析：二分图最大匹配与应用

"这篇代码是关于杭电ACM竞赛中的一个问题，题目编号HDOJ-1150，实现的是匈牙利算法求解二分图的最大匹配问题。" 二分图及其应用在ACM程序设计中占据着重要的地位，特别是在解决匹配问题时。二分图是指一个图的节点可以被分成两个不相交的集合X和Y，所有边都连接不同集合的节点。例如，可以将二分图应用于婚配问题，其中一边代表男性，另一边代表女性，边表示两人之间的匹配可能性。 最大匹配问题是在二分图中寻找尽可能多的、不相交的边，使得每个节点最多只参与一条边。这在实际问题中有着广泛的应用，如任务分配、资源调度等。 匈牙利算法是一种解决二分图最大匹配的有效方法。算法的核心思想是通过深度优先搜索（DFS）寻找可增广路径，即能找到一条从未匹配节点到未匹配节点的路径，使得路径上的每条边在当前匹配中都没有被使用，或者使用后能增加匹配数量。如果找到这样的路径，就更新匹配，然后继续寻找新的可增广路径，直到无法找到为止。 给出的代码中，`Solve()`函数实现了匈牙利算法的过程。首先，它初始化两个数组`mark1`和`list`，`mark1`用于标记集合X中的未匹配节点，`list`记录每个节点的匹配伙伴。然后，通过两层循环尝试为每个节点寻找匹配，使用DFS进行深度搜索。在DFS过程中，如果找到了一条可增广路径，就会更新匹配并继续搜索。最后，根据`list`数组和未匹配节点的数量，输出最大匹配数。 代码中的`main()`函数负责读取输入，构建二分图，并调用`Solve()`求解最大匹配。当输入的图为空时，程序终止。 在实际编程竞赛或算法设计中，理解并熟练运用匈牙利算法是解决二分图问题的关键，因为它能够确保找到一个最大匹配，且复杂度相对较低，适用于大多数实际场景。此外，二分图的其他应用还包括最小顶点覆盖、最小路径覆盖和最大独立集等问题，这些都可以通过转化成匹配问题来解决。