通俗易懂的匈牙利算法

最近复习算法的时候,发现好多讲匈牙利的教材都讲的特别恶心,其实这是一个非常容易理解的算法。

匈牙利算法主要是求二分图的最大匹配

主要思想是把左边的一个个匹配,冲突就尝试给前面的分配另一个点

下面是详细解析

我们有四位同学,四个座位,每个同学都有自己喜欢的座位
这里写图片描述

首先是1号
1号同学直接坐在了A座位上

然后到2号
2号同学也直接坐在了B座位上

到了3号
我的B座位居然给你2号占了,给我起来

2号同学的屁股暂时从B座位上挪了下来

我们重新给2号找一个位置
2号发现,诶,C座位没人,我坐
3号也坐在了B座位上

到了4号
那D座位就是我的啦

至此,所有同学圆满归位(此处应有热烈掌声)

明白了吗?

下面是代码,还不懂的可以借助代码理解

bool find(int k)
{
    int i,j;
    fo(i,1,a[k][0])//枚举K号同学能够做的
    {
        int p=a[k][i];
        if (bz[p]==0)//如果我们这次改变还没有尝试过给P座位换主人
        {
            bz[p]=1;//如果尝试过了后面的递归就不用再麻烦了
            if (dt[p]==0||find(dt[p])) //如果P座位还没有人或者能把P座位上的人换个地方
            {
                dt[p]=k;//那就坐下呗
                return 1;
            }
        }
    }
    return 0;
}
//下面是主程序的主要部分
fo(i,1,n)一个个人分配
    {
        memset(bz,0,sizeof(bz));
        if (find(i)) s++;//如果他能坐下,答案+1
    }
相关文章
相关标签/搜索