数据结构与算法学习笔记----匈牙利算法
@@ author: 明月清了个风
@@ first publish time: 2024.12.22ps⛹️♀️这题的算法思路在题目中，没有写在题目前面，注释十分详细
Acwing 861. 二分图的最大匹配
[原题链接](861. 二分图的最大匹配 - AcWing题库)
给定一个二分图，其中左半部包含 n 1 n_1 n1个点（编号 1 ∼ n 1 1 \sim n_1 1∼n1），右半部包含 n 2 n_2 n2个点（编号 1 ∼ n 2 1 \sim n_2 1∼n2），二分图共包含 m m m条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配，给定一个二分图 G G G，在 G G G的一个子图 M M M中， M M M的边集 { E } \{ E\} {E}中的任意两条边都不依附于同一个顶点，则称 M M M是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n 1 n_1 n1、 n 2 n_2 n2和 m m m。
接下来 m m m行，每行包含两个整数 u u u和 v v v，表示左半部点集中的点 u u u和右半部点集中的点 v v v之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
1 ≤ n 1 , n 2 ≤ 500 1 \leq n_1, n_2 \le 500 1≤n1,n2≤500,
1 ≤ u ≤ n 1 1 \le u \le n_1 1≤u≤n1,
1 ≤ v ≤ n 2 1 \le v \le n_2 1≤v≤n2,
1 ≤ m ≤ 1 0 5 1 \le m \le 10^5 1≤m≤105
思路
首先是二分图的概念，具体的可以看染色法判定二分图。
简单来说，二分图就是将所有的点分为两部分，且所有的边连接的两点分别在这两部分中，两个点集内部不存在边。
由此就有了二分图的最大匹配问题，也就是找到一个边的集合，这些边所连接的每个点都只使用了一次且要求这个集合所含的边数最多。
匈牙利算法是用来解决这个问题的一个适用算法，核心思想是利用增广路径来增加匹配数。
基本步骤:
- 初始化，所有顶点没有匹配
- 针对每个未匹配的点，寻找增广路径
- 更新匹配，如果对于一个点找到了增广路径，那么就反转路径上的匹配状态
- 停止的条件就是查找路径失败。
可以看成是给左半部的男的找对象的过程：对于每个左半部的男生，可能会对多个右边的女生心仪，这就是边的概念，那么为他找一个女生，并记录在match[]数组中，意味着一个女生的男朋友是谁，那么对于下一个男生，他也对刚刚这个女生心仪，并且他也只对这个女生心仪（也就是这个点只有一条出边），那么就要尝试为这个女生目前的对象(记录在match[]中)重新找一个女生(因为原来的对象有多条出边)，如果成功，那么现在就有两对情侣了，失败，那就还是只有一对。
注意点：
下面的代码中有一个st[]数组感觉理解起来可能有点困难，这里讲一下我自己的理解
匈牙利算法其实会遍历所有左边的n1个点，也就是寻找n1轮，但是寻找的过程中需要使用st[]数组进行标记，表示每一个右边的女生在一轮搜索中是否已经有了对象
可以看find函数中的过程：
-
首先会遍历
find(x)的x所有出边for(int i = h[x]; i != -1; i = ne[i])，找到他心仪的女生j = e[i]。 -
那么对于这个女孩只有两种情况：
- 一种是没有对象
match[j] == 0，那么当前男生x直接成为她的对象就行了mathch[j] = x。 - 另一种是有对象
match[j] = y，但是他的这个对象有对个心仪的女孩，而且我们还成功给他重新找了另一个find(y) == true。
那么对于上述两种情况，女孩的对象最后都是
x，对于这个find(x)来说，也就是成功增加了一个匹配。 - 一种是没有对象
-
上面两种情况中的第二种情况就导致我们需要记录每个女孩的
st，因为可以看出，find是一个递归的过程，我们现在在为x招对象，发现x喜欢j但是j有对象y，我们的解决方案是给y重新找一个，那么递归find(y)，y又会遍历他的所有出边，那就会再次找到j，但是目前的矛盾情况就是j，因此我们需要跳过他，跳过的方法就是st[]数组。
时间复杂度
根据下面的代码可以看出，会遍历所有左半部的点，最多遍历 m m m条边，因此理论时间复杂度为 O ( n ∗ m ) O(n*m) O(n∗m)
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 510, M = 100010;int h[N], e[M], ne[M], idx; // 邻接表存图
int match[N]; // 存储右半部集合的每个顶点的匹配点，match[i]==0表示未匹配
bool st[N]; // 用于记录某个顶点在一轮搜索中是否被访问过了
int n1, n2, m;void add(int a, int b) // 建图的加边操作
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}bool find(int x) // 其实是一个DFS的过程
{for(int i = h[x]; i != -1; i = ne[i]) // 遍历点x的所有邻点j{int j = e[i];if(!st[j]) // 点j没有被访问过就尝试增加匹配{st[j] = true; // 标记点jif(match[j] == 0 || find(match[j])) // 两种状态，一种是没有匹配对象，一种是能够为点j原来的匹配对象重新找一个匹配对象{match[j] = x; // 没有匹配对象或重新找对象成功，那就将j作为当前点x的对象。return true;}}}return false;
}int main()
{cin >> n1 >> n2 >> m;memset(h, -1, sizeof h);for(int i = 0; i < m; i ++){int a, b;cin >> a >> b;add(a, b);}int res = 0;for(int i = 1; i <= n1; i ++) // 遍历所有的点，尝试为每个点都找对象{memset(st, false, sizeof st); // 找对象前要清空st，st表示的每一轮dfs的访问标记。if(find(i)) res ++;}cout << res << endl;return 0;
}
