保证绝大多数人的利益——匈牙利算法

$\color{red}\text{匈牙利算法}$是一种在多项式时间内求解任务分配问题的组合优化算法,并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法,是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来。(摘自百度百科

总的来说,匈牙利算法主要的用途是将多个任务尽可能多的分配给多个对象,在算法竞赛中主要用于求解二分图最大匹配等问题。

如果你不明白什么是二分图匹配,不妨看看下面这个例子。

幼儿园里现在有4个小朋友,摆在他们面前是四种食物,分别是棒冰、汉堡、薯片、炸鸡,现在要把这些食物分给小朋友们吃。根据调查,在我国改革开放、经济发展的前提下,现在的小朋友都吃得饱饭,所以他们都会挑食(但是好像没有人不吃垃圾食品)。他们的喜好大致是这样的:

条件

我们把小朋友和食物看成分为两边的点,组成的图便是$\footnotesize\color{red}\text{二分图}$,而我们分配的过程就是$\footnotesize\color{red}\text{匹配}$。如果能把所有的食物都分配给小朋友,没有浪费,每个小朋友都开心,这自然是最吼的,这种情况也被称为$\footnotesize\color{red}\text{完美匹配}$。但事实显然不是次次都尽人意,所以只能让更多的小朋友开心,因为小朋友不高兴了实在是太麻烦了,开心的小朋友最多的情况就达到了$\footnotesize\color{red}\text{最大匹配}$。

为了让小朋友们感受异国风情,你决定受用匈牙利人的方法来分配。首先先考虑第1个小朋友,他喜欢棒冰,那就我们把棒冰给他。

分配1

接下来看第2个小朋友,他喜欢吃的是汉堡,而此时汉堡又名花无主,所以直接就把汉堡给他(汉堡:w(゚Д゚)w)。

分配2

然后是3号小朋友,棒冰是他的最爱。等等!棒冰以及被1号小朋友拿走了!!!为了让3号小朋友不哭,我们决定从1号小朋友手中夺走拿来棒冰(1号小朋友:Σ(っ °Д °;)っ)。

分配3

(绿色表示棒冰暂时被拿走了)

看看1号小朋友能不能换一个东西吃,发现1号小朋友还喜欢汉堡,但是汉堡已经在2号小朋友的手中了,于是我们只好重复之前的步骤,发现最后可以让3个小朋友都开心,于是皆大欢喜。

分配4

最后是4号小朋友,我们试着给像对3号小朋友那样给4号小朋友分到他想要的食物,只是可惜没有成功。本着先到先得的原则,我们只好把暂时拿走的食物还给其他小朋友,留给4号小朋友的只有一个爱的抱抱了(4号小朋友:╥﹏╥...)。于是最终的情况变成了这样:

分配5

这样先到先得,尝试给后来的小朋友腾出食物,尽可能让更多小朋友开心的分配方式,就是用匈牙利算法求解二分图的最大匹配。

接下来是代码实现:

bool find(int now)
{
    for(int i=head[now];i!=0;i=e[i].nxt) //使用邻接表储存边(小朋友喜好)的信息
        if(vis[e[i].to]==false) //如果这个节点(食物)这次没有被调度过
        {
            vis[e[i].to]=true;
            if(p[e[i].to]==0 || find(p[e[i].to])) //如果这个节点(食物)没有被匹配或者可以给这个现在匹配的节点(小朋友)找到一个新的匹配
            {
                p[e[i].to]=now;
                return true;
            }
        }
    return false; //找不到就返回失败
}

for(int i=1;i<=n;i++) //主程序
{
    memset(vis,false,sizeof(vis));
    if(find(i)==true) ans++;
}

实现代码以后就是喜闻乐见的好题推荐环节了!

P3386 【模板】二分图匹配

P1640 [SCOI2010]连续攻击游戏

P3231 [HNOI2013]消毒


发表于 2019-07-18 16:29:10 in 算法