匈牙利算法详解：高效求解二分图最大匹配

二分图匹配的匈牙利算法是一种经典的图论方法，用于在二分图中找到最大的匹配。在计算机科学中，二分图是指一个顶点集V分为两个独立的集合V1和V2，边集E仅连接V1中的顶点与V2中的顶点。最大匹配问题的目标是找出一个没有互相冲突的边的最大子集，即在一个匹配中，每条边都不与其他匹配的边共用任何顶点。 匈牙利算法，也称为Munkres算法，是由John Edmonds在1955年提出的，它提供了一种系统的方法来解决这个问题，特别是对于有向图，但可以扩展到二分图。算法的核心思想是通过增广路径（augmenting path）来逐步改进匹配，直到达到一种局部最优状态，即不可能再增加匹配的大小。 在给出的代码片段中，我们看到以下关键部分： 1. 定义全局变量： - `n` 和 `m` 分别表示二分图的顶点数和边数。 - `match[MAX]` 是一个数组，用于存储当前的匹配状态，-1表示未匹配，其他值表示匹配的顶点。 - `visit[MAX]` 是一个布尔数组，用于记录哪些顶点已经被访问过。 - `map[MAX][MAX]` 是一个二维布尔数组，表示是否有边连接两个顶点。 2. `dfs(int k)` 函数是深度优先搜索的实现，参数 `k` 表示当前正在处理的顶点。函数遍历 `map` 数组，如果发现一条边 `(k, i)` 且 `i` 未被访问，并且 `match[i]` 为空或者可以通过递归调用 `dfs` 得到匹配，那么这条边就被加入到匹配中，然后回溯更新 `match` 数组。 3. `FindAns()` 函数是整个算法的核心，它初始化匹配数组为 -1，然后对每个顶点 `i` 进行深度优先搜索。如果能成功找到一个增广路径，就将答案 `ans` 增加1。最后返回 `ans`，即最大匹配的顶点数量。 整个过程可以通过迭代的方式进行，直到无法找到增广路径为止。匈牙利算法的时间复杂度是O(n^3)，虽然在网络流方法（如Ford-Fulkerson算法）的启发下可能更高效，但对于特定的二分图结构，匈牙利算法仍具有实用性和易于理解的优势。该算法不仅在理论上有重要意义，也被广泛应用于实际问题，如任务分配、资源调度等领域。