【题目来源】
【题目描述】
给定一个二分图，其左部点的个数为 n，右部点的个数为 m，边数为 e，求其最大匹配的边数。
左部点从 1 至 n 编号，右部点从 1 至 m 编号。
【输入格式】
输入的第一行是三个整数，分别代表 n，m 和 e。
接下来 e 行，每行两个整数 u，v，表示存在一条连接左部点 u 和右部点 v 的边。
【输出格式】
输出一行一个整数，代表二分图最大匹配的边数。
【输入样例一】
1 1 1
1 1
【输出样例二】
1
【输入样例二】
4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1
【输出样例二】
2
【数据规模与约定】
对于全部的测试点，保证：
1≤n,m≤500，1≤e≤5×10^4。
1≤u≤n，1≤v≤m。
不保证给出的图没有重边。
【算法分析】
● 二分图的概念：如果无向图 G=(V, E) 的所有点可以分为两个集合 V1，V2，所有边都在 V1 与 V2 之间，且 V1，V2 的内部都没有边，则称 G 是一个二分图。
● 一个图是否为二分图，一般用“染色法”进行判断。染色法的核心思想非常直观：尝试用两种颜色对图中的所有顶点进行着色，并确保任何一条边两端的顶点颜色都不相同。如果能成功完成着色，则该图是二分图；否则，不是。
● 染色法的算法流程通常基于 BFS 或 DFS 实现。
（1）选择一种颜色（如 0）作为起始颜色。
（2）从一个未访问的节点开始，将其染色，然后遍历其所有邻居。
（3）若邻居未染色，则将其染成与当前节点相反的颜色（如 1），并递归（DFS）或入队（BFS）处理。
（4）若邻居已染色，则检查其颜色是否与当前节点相反。若颜色相同，则说明存在奇环，该图不是二分图。
● 匈牙利算法是解决“二分图最大匹配”问题的专精算法，由匈牙利数学家 Edmonds 于 1965 年提出，其主要功能是「求二分图的最大匹配的数量」。
● 匈牙利算法的冲突处理逻辑
设集合 U 和 V 为二分图的两个顶点集，M 为当前匹配集合。当元素 x∈U 需要与元素 y∈V 匹配，但 y 已与元素 z∈U 匹配时，算法的冲突处理逻辑为：
（1）检查元素 z 能否与集合 V 中其他元素 c（c≠y）形成新的匹配。
（2）若存在这样的元素 c，则将匹配关系调整为 (z,c) 和 (x,y)。
（3）若不存在，则继续为 x 寻找 V 集合中的其他匹配候选。
显然，匈牙利算法冲突处理的逻辑是“后来者居上”、“腾位子”。
● 匈牙利算法的示例
俗话说，“男女搭配，干活不累”。已知二分图的一部分是“男生集合”，另一部分是“女生集合”。若把具有好感的男女生匹配为“干活搭子”，请问最多能匹配成多少对儿？这就是匈牙利算法要解决的问题。（备注：具有好感的男女生已用线在二分图中进行了连接）
（1）遍历到 1 号男生，发现他和 2 号女生具有好感。因此，将他俩连一条红线配成“干活搭子”。
（2）遍历到 2 号男生，发现他和 1 号女生具有好感，因此，将他俩连一条红线配成“干活搭子”。
（3）遍历到 3 号男生，发现他和 2 号女生具有好感，但是 2 号女生已经和 1 号男生配对了。
怎么办？观察易知，1 号男生还和 4 号女生具有好感。那么问题就简单了。解决方法是给 1 号男生和 2 号女生连一条绿线，标示他们分开。然后再把 1 号男生和 4 号女生连一条红线配成“干活搭子”，3 号男生和 2 号女生连一条红线配成“干活搭子”。此番操作，都有配对，皆大欢喜。
（4）遍历到 4 号男生，发现他和 3 号女生具有好感。因此，将他俩连一条红线配成“干活搭子”。最后，获得最大匹配数量为 4 对。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=5e2+5,M=5e4+5;
int e[M],ne[M],h[N],idx;
int mate[N],st[N];void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}bool HA(int u) { //Hungarian Algorithmfor(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(!st[j]) {st[j]=true;if(!mate[j] || HA(mate[j])) {mate[j]=u;return true;}}}return false;
}int main() {memset(h,-1,sizeof h);int n,m,e;cin>>n>>m>>e;while(e--) {int u,v;cin>>u>>v;add(u,v);}int cnt=0;for(int i=1; i<=n; i++) {memset(st,false,sizeof st);if(HA(i)) cnt++;}cout<<cnt<<endl;return 0;
}/*
in:
4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1out:
2
*/
【参考文献】