二分图匹配算法（C++实现）

"二分图匹配算法（C++实现）" 二分图匹配算法是图论中的一个重要问题，它是指在一个二分图中寻找最大匹配的算法。最大匹配是指在图中找到最多的匹配边的集合，且这些边不相交。 本文将详细介绍匈牙利算法和KM算法，这两个算法都是解决二分图匹配问题的经典算法。 基本概念 在二分图匹配算法中，需要了解一些基本概念： * 匹配集合M：是一组边的集合，且这些边不相交。 * 未盖点：不与任何一条属于M的边相连的点。 * 交错轨：属于M的边与不属于M的边交替出现的轨（链）。 * 可增广轨：两端点是未盖点的交错轨。 匈牙利算法 匈牙利算法是解决二分图匹配问题的经典算法。该算法的时间复杂度为O(|V||E|)。 原理： 寻找M的可增广轨P，P包含2k+1条边，其中k条属于M，k+1条不属于M。修改M为M&P。即这条轨进行与M进行对称差分运算。 实现： 关于这个实现，有DFS和BFS两种方法。先列出DFS的代码： ```c bool dfs(int x) { for (int i = 1; i <= m; i++) { if (map[x][i] && !mk[i]) { mk[i] = true; int t = match[i]; match[i] = x; if (t == 0 || dfs(t)) return true; match[i] = t; } } return false; } int hungarian() { int max_ = 0; F(i, 1, n) { memset(mk, false, sizeof(mk)); if (dfs(i)) max_++; } return max_; } ``` KM算法 KM算法是另一个解决二分图匹配问题的经典算法。该算法的时间复杂度为O(|V||E|)。 原理： 寻找M的可增广轨P，P包含2k+1条边，其中k条属于M，k+1条不属于M。修改M为M&P。即这条轨进行与M进行对称差分运算。 实现： 关于这个实现，同样有DFS和BFS两种方法。这里不再列出代码。 二分图匹配算法是图论中的一个重要问题，它有很多实际应用，如人员分配、物流配送等。匈牙利算法和KM算法是解决这个问题的经典算法，具有很高的时间效率和空间效率。