给定一个二分图，其中左半部包含 n1𝑛1 个点（编号 1∼n11∼𝑛1），右半部包含 n2𝑛2 个点（编号 1∼n21∼𝑛2），二分图共包含 m𝑚 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图 G𝐺，在 G𝐺 的一个子图 M𝑀 中，M𝑀 的边集 {E}{𝐸} 中的任意两条边都不依附于同一个顶点，则称 M𝑀 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1𝑛1、 n2𝑛2 和 m𝑚。
接下来 m𝑚 行，每行包含两个整数 u𝑢 和 v𝑣，表示左半部点集中的点 u𝑢 和右半部点集中的点 v𝑣 之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
1≤n1,n2≤5001≤𝑛1,𝑛2≤500,
1≤u≤n11≤𝑢≤𝑛1,
1≤v≤n21≤𝑣≤𝑛2,
1≤m≤105
思路：就是看n1中的点是否有n2中的点和其配对，若有未配对的点，则一定可以配对，此时匹配数加一。若当前点已经和n1中点j进行了配对，则考虑点j能不能换n2中别的点进行配对，若可以则匹配数加一，若始终不能有配对的点，则匹配数不变。
本题要注意的点：
1.判断是否有别的点和j配对的时候，复用了配对函数
2.注意复用函数里面只能配对别的点，不能说在对这个n2中的点尝试让其他点换一个，即对于n2中的每一个点，在一次完整的配对过程中只能配对一次，用数组v记录n2中的点是否已经尝试过配对。每次遍历n1的点前都先让n2中所有点尝试配对状态时false，每次找n2中的点，若尝试找别的配对点，都先将n2中该点状态置为true。
#include<iostream>
#include<cstring>using namespace std;
const int N=100010;
int h[N],e[N],idx,ne[N];
int per[510];
int m,n1,n2;
bool v[510];
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool monk(int u)
{ for(int j=h[u];j!=-1;j=ne[j]){ int t=e[j];if(!v[t]){ v[t]=true;if(!per[t]||monk(per[t])){per[t]=u;return true;}}}return false;
}
int main()
{ memset(h,-1,sizeof h);scanf("%d%d%d",&n1,&n2,&m);while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b);}int ans=0;for(int i=1;i<=n1;i++){ memset(v,false,sizeof v);if(monk(i))ans++;}printf("%d\n",ans);return 0;
}
