二分图最大匹配
设 G为二分图，若在 G 的子图 M中，任意两条边都没有公共节点，那么称M为二分图G的一组匹配。在二分图中，包含边数最多的一组匹配称为二分图的最大匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，若能到达另一个未匹配点，则这条交替路称为增广路。
例如，3→5→1→4→2→7
如下图所示：
观察增广路，我们会发现：非匹配边比匹配边多一条。只要把增广路中的匹配边和非匹配边的身份交换(即倒过来走)，交换后，图中的匹配边数目比原来多了1条。
如图所示：
这里的增广路就是指能增加匹配边的一条路。
匈牙利算法：通过不停地找增广路来增加匹配边。找不到增广路时，达到最大匹配。可以用DFS或BFS来实现。
匈牙利算法
男女相亲，男选女，可占可让，贪心配对
我们来看一道例题：
洛谷P3386
代码如下：
#include<iostream> // 引入输入输出库
using namespace std;
// 声明全局变量
int n, m, k, a, b, ans; // n: 左边节点数, m: 右边节点数, k: 边数, a, b: 边的两个端点, ans: 匹配的总数
const int M = 500005; // 定义最大边数
const int N = 500005; // 定义最大节点数
int h[N], idx; // h: 邻接表头, idx: 当前边的索引
int vis[N], match[N]; // vis: 访问标记数组, match: 匹配数组
// 边的结构体定义
struct edge {
int v; // 边的终点
int ne; // 下一个边的索引
} e[M]; // 声明边的数组
// 添加边到邻接表
void add(int a, int b) {
e[++idx] = { b,h[a] }; // 将边(b, h[a])加入数组e，并更新邻接表
h[a] = idx; // 更新节点a的邻接表头指向当前边
}
// 深度优先搜索尝试寻找增广路径
bool dis(int u) {
// 遍历以u为起点的所有边
for (int i = h[u]; i; i = e[i].ne) {
int v = e[i].v; // 获取边的终点v
if (vis[v]) { // 如果v已经被访问过
continue; // 跳过
}
vis[v] = 1; // 标记v为已访问
// 如果v没有匹配或者找到v的匹配节点的增广路径
if (!match[v] || dis(match[v])) {
match[v] = u; // 更新v的匹配为u
return 1; // 找到一条增广路径
}
}
return 0; // 未找到增广路径
}
int main() {
cin >> n >> m >> k; // 输入左边节点数n、右边节点数m和边数k
for (int i = 0; i < k; i++) { // 遍历每一条边
cin >> a >> b; // 输入边的两个端点a和b
add(a, b); // 添加边到邻接表
}
for (int i = 1; i <= n; i++) { // 对于每一个左边节点
memset(vis, 0, sizeof(vis)); // 重置访问标记数组
if (dis(i)) { // 尝试从节点i出发寻找增广路径
ans++; // 如果找到增广路径，匹配数增加
}
}
cout << ans << endl; // 输出最终的匹配数
return 0; // 返回0，程序正常结束
}