地址 https://www.acwing.com/problem/content/description/863/
给定一个二分图，其中左半部包含n1n1个点（编号1~n1n1），右半部包含n2n2个点（编号1~n2n2），二分图共包含m条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1n1、 n2n2 和 mm。
接下来m行，每行包含两个整数u和v，表示左半部点集中的点u和右半部点集中的点v之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
1≤n1,n2≤5001≤n1,n2≤500,
1≤u≤n11≤u≤n1,
1≤v≤n21≤v≤n2,
1≤m≤105
输入样例： 2 2 4 1 1 1 2 2 1 2 2 输出样例： 2
解法
二分图最大匹配的模板
左右两边的点 我们只需要关注一边的点即可
以左边点为例
第一个点选取第一个可连接的右边的点 然后看第二个点
如果两点的连接的右边的点有冲突，则其中一个点尝试选择其他可连接的右边的点
如果上述过程全部执行完 所有点均找到可以匹配的右边的点 或者无其他选择 则结束
代码
1 #include <iostream> 2 #include <vector> 3 #include <memory.h> 4 5 6 using namespace std; 7 8 const int N = 510; 9 const int M = 100010; 10 11 int n1, n2, m; 12 int match[N]; 13 bool st[N]; 14 15 vector<int> v[2*N]; 16 17 int find(int x) 18 { 19 for (int i = 0; i < v[x].size(); i++) { 20 int j = v[x][i]; 21 if (!st[j]) { 22 st[j] = true; 23 if (match[j] == 0 || find(match[j])) 24 { 25 match[j] = x; 26 return true; 27 } 28 } 29 } 30 return false; 31 } 32 33 int main() 34 { 35 cin >> n1 >> n2 >> m; 36 37 while (m--) { 38 int a, b; 39 scanf("%d%d",&a,&b); 40 //cin >> a >> b; 41 v[a].push_back(b); 42 } 43 int res = 0; 44 for (int i = 1; i <= n1; i++) { 45 memset(st, false, sizeof(st)); 46 if (find(i)) res++; 47 } 48 49 //cout << res << endl; 50 printf("%d\n",res); 51 52 return 0; 53 }