解题报告 P3386 【模板】二分图最大匹配

二分图

二分图，是指节点由两个集合组成，且两个集合内部没有边的图。

图 G 的一个匹配是由一组没有公共端点的不是圈的边构成的集合。

二分图的最大匹配就是尽量让二分图的左部和右部都存在尽可能多的点一一对应

匈牙利算法

求解二分图最大匹配一般使用匈牙利算法

匈牙利算法的过程是，每次枚举每一个左部点 u ，然后枚举该左部点连出的边，对于一个出点 v，如果它没有被先前的左部点匹配，那么直接将 u 匹配到 v，否则尝试让 v 的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将 u 匹配 v，否则 u 无法被匹配。

如上匹配的过程是一个递归的过程，

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{...}

const int maxn=505;
int n,m,e;
int G[maxn][maxn];
int right[maxn];
bool used[maxn];

bool find(int x)
{
    for(int j=1;j<=m;j++)
    {
        //used数组表示在尝试匹配x号左部点的时候，j号右部点有没有被尝试更改过匹配
        if(G[x][j] && (!used[j]))//如果这个右部点还没有被动过，尝试动他
        {
            used[j]=1;//表示动过了
            if((!right[j]) || find(right[j]))//此处意为如果该右部点没有被匹配过或者成功改变了它的原匹配
            {
                right[j]=x;//right[j]存储j号右部点匹配到的左部点
                return true;
            }
        }
    }
    return false;
}

int main()
{
    n=read(),m=read(),e=read();
    for(int i=1;i<=e;i++)
    {
        int u=read(),v=read();
        G[u][v]=1;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(used,0,sizeof used);
        if(find(i))//如果i点能成功匹配
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}