二分图匹配--匈牙利算法

匈牙利算法

算法思想

有两个集合,有一些关系

模板

int n,m,e;
int a[maxn][maxn];      //关系
bool vis[maxn];         //是否询问过了
int match[maxn];        //匹配,match[i]表示第i个男生匹配的女生


int find(int x)     //第x个女生
{
    for(int i = 1; i <= n; i++)     //对于全部的男生
    {
        if(!vis[i] && a[i][x])  //如果第i个男生没有询问过,并且对x有好感
        {
            vis[i] = 1;         //询问
            if(match[i] == -1 || find(match[i]))    //这个男生没有对象,或者这个男生的对象可以换另一个男生
            {   
                match[i] = x;  //第i个男生匹配x女生
                return 1;
            }
        }
    }
    return 0;
}


//mian函数里面
for(int i = 1; i <= m; i++)
{   
    mem(vis,0);         //vis数组清空
    ans += find(i);
}

模板题

https://www.luogu.com.cn/problem/P3386

参考博客

https://blog.csdn.net/lw277232240/article/details/72615522

二分图匹配--匈牙利算法

原文：https://www.cnblogs.com/hezongdnf/p/12027677.html