算法（ 二分图的最大匹配）

给定一个二分图，其中左半部包含 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;
}