匈牙利算法是二分图匹配的一个简单算法.

算法的实现方式:

1.遍历左部点,观察是不是存在这个点所连的增广路劲,假如存在ans++.
2.找增广路径,判断其是否为自己相连的点,假如是假如这个点还没被连接或是这个点可以让原来连接它的点寻找新的连接点的话,我们就连接它.然后找到即结束.

证明:

采用反证法,假如说还有一条边可以连接.
那么它的连接方式无法两种,一种是直接连接(显然是不可能存在这种情况的.),第二种是间接连接,那么就和我说的找增广路径矛盾,至此就证明了,当前匹配一定是最大匹配.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=505;
bool vis[N][N],f[N];//判断u,v点是否有边.
int n,m,e,match[N];//左部点数 右部点数 二分图边数 右部点匹配的左部点id. 
int dfs(int u)
{
    for(int i=1;i<=m;i++)
    {
        if(vis[u][i]&&!f[i])
        {
            f[i]=true;
            if(!match[i]||dfs(match[i]))
            {
                match[i]=u;
                return 1;
            }
        }
    }return 0;
}

int main()
{
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        vis[u][v]=true;
    }int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(dfs(i))    ans++;
        memset(f,0,sizeof f);
    }printf("%d\n",ans);
    return 0;
}

时间复杂度：

其中是左边点的点数,是二分图的边数.