匈牙利算法-二分图最大匹配问题

https://www.luogu.org/problemnew/show/P3386

#include<cstdio>
int e[1005][1005],match[1005],book[1005]; // match数组用来记录配对关系 
int n,m,t;
int dfs(int u)
{
    for(int v=1; v<=m; v++)
    {
        if(book[v]==0&&e[u][v]==1)
        {
            book[v]=1; // 标记v点已经被访问 
            if(match[v]==0||dfs(match[v])) // 如果点v未被配对,或者点v的匹配对象找到了新的配对。 
            {
                match[v]=u; // 更新配对关系 
                return 1;
            }
        }
    }
    return 0;
}
int main()
{

    int a,b;
    int sum=0;
    scanf("%d%d%d", &n, &m, &t);
    while(t--)
    {
        scanf("%d%d", &a, &b);
        if(a>n||b>m)
            continue;
        e[a][b]=1;
    }
    for(int i=1; i<=n; i++) // 判断每一个左边的点能不能与右边的点形成一个新的增广路(一条路径的起点、终点都是未被配对的点), 
    {
        for(int j=1; j<=n; j++)
            book[j]=0; // 清空上次搜索时的标记 
        if(dfs(i))
            sum++;// 可以的话匹配数+1。 
    }
    printf("%d", sum);
}

 

上一篇:洛谷1005(dp)


下一篇:PAT Basic 1005