前言

前些时间康了一下染色法判定二分图的板子,那今天就来说说关于二分图的另外一个算法:

匈牙利算法。


相关芝士


简单介绍一下概念。

二分图,就是能(把图中的点分为$U,V$两个集合,且图中的边只在$U,V$之间出现)的图。也就是对于分出的集合来说,集合内部不能有边。能分出来的图就是二分图。

另外的一种定义是:不含有「含奇数条边的环」的图。

比如这是一张二分图:

g1.png

但是我们一般将其明显表示为二分图,就把两个集合的点放置在两边,就像这样:

g2.png

以上。

匹配,即一个边的集合,在这个边的集合中,任意两条边都没有公共顶点。比如下图中的蓝边就是一个[匹配]。

g3.png

懂了匹配的概念,还要引入几个浅显的概念:匹配点,匹配边,未匹配点,非匹配边


匹配点就是由这个匹配(一定要记住“匹配”是一个边的集合)中的边所连起来的点,没有被连起来的就是未匹配点匹配边非匹配边同理。

最大匹配,所有的匹配中,所包含的边数最多的匹配。

补充概念:我也不懂

完美匹配,即每个左边集合中的点都可以通过匹配中的边找到一个唯一的右边集合中的点。当然,当所有点都是匹配点的时候,这个匹配就是一个完美匹配。

交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替 路称为增广路(agumenting path)。

下图的蓝边就是一个完美匹配的例子:

g4.png


以上就是要了解的基本概念。(二分图,匹配,匹配点,匹配边,未匹配点,非匹配边,最大匹配

匈牙利算法,就是来解决求最大匹配包含的边的数量的算法。

让我们来通过实例(真)感性地理解一下算法流程。

以这个图片为例:

g5.png

为了形象,我们把左边的点看做男孩们,右边的点就是女孩们,连边表示他们互相有好感海王出来挨打。现在要让你当这个月老,凑更多的cp祸害人间

开始你的炸弹秀 题目链接

模拟开始!

首先来给男孩1找对象,首先找到女孩5,发现她没有被匹配,于是暂时让他们成为一对,并且记录现在女孩5的对象是男孩1.

然后就轮到男孩2了。很可惜,他所钟意的女孩5已经被暂时选中了,但是不能怂啊,于是我们找到女孩5的对象男孩1,让他试试能不能换一个(是的没错),然后发现男孩1可以匹配女孩6,那么就把1和6匹配起来,5就归2了。

这不是一个悲伤的故事

男孩3顺利匹配到名花无主的女孩8.

最后一个男孩4所连向的女孩5也已经被选中了,那这次我们再去看看原配2能不能换一个(霸气),但是非常悲伤的是,2已经走投无路莫得选择了,所以男孩4很遗憾地失配了。

所以这张图中的最大匹配就是上图中的三条边。

模拟结束


可以发现,在这个找妹子的过程中,我们始终坚持能让就让,这就是匈牙利算法的核心思想。

另外,对于这个腾位置的过程也是递归的,比如回去找到原配要求换的过程中,可能还会牵扯到另外的一些调整关系(就是乱)


代码部分

int pre[510];
//[已经确定被匹配]的点的前驱
bool used[510];
//在[当前尝试的匹配]中被选中的标记

//尝试加入点u看是否能合理调整之后让匹配中边数更多
bool find(int u)
{
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(used[v])continue;
        //update:2020-5-30
        //这里标记是为了保证在腾出位置的时候
        //其他点无法选中这个要腾出来的点
        //在递归过程中也可以避免多个左部点选中一个右部点
        used[v]=1;
        if(!pre[v]||find(pre[v]))
        {
            pre[v]=u;
            return 1;
        }    
    }
    return 0;
}
//在主函数中:
for(int i=1;i<=n;i++)
{
    memset(used,false,sizeof used);
    //对于每一轮,我们遍历过的另一边的点都不需要再次遍历了,但是每一轮之间是相对独立的。所以每次要进行初始化。
    if(find(i))cnt++;
    //如果加入当前这个点能让匹配的边数增加,干就完了。
}
    //最终的cnt就是最大匹配包含的边数

在递归过程中其实也进行了腾位,具体可以请读者自行模拟一下我懒就不给大家画了(咕了)

$update:2020-5-17$

更新一个小优化。

我们在每一次find一个点的时候,都进行了一次memset,花费的时间显然是有点多的,那能不能在这一步进行优化呢?

我们发现,在前一轮即使被遍历过的点,在这一轮也是没有影响的。但如果是这一轮被遍历的点,就不需要再遍历一次了。

于是我们可以想办法不清空used数组,但又需要区分这两个标记是否是在同一轮尝试中打上去的。所以可以考虑通过一个int类型的used数组,每一轮打上一个类似于时间戳的标记,第一轮打1,第二轮打2..以此类推。

这样就可以节约下n次memset的时间了。

代码块:

int pre[2000010];
int used[2000010];
//数组意义同上
int tag;
bool find(int u)
{
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(used[v]!=tag)
        {
            used[v]=tag;
            if(!pre[v]||find(pre[v]))
            {
                pre[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
//每次在进入尝试之前需要改变全局变量tag的值,这样保证每一轮的标记不同就好。

练习&各种定理篇


König定理

二分图最大匹配的König定理及其证明 By matrix67

基础学习是从这篇博文里面学的,下面码一下自己的理解。

定理内容:二分图的最小点覆盖集=二分图的最大匹配

注意前提:在二分图中。

相关定义:什么是点覆盖集?

点覆盖:就是一个点集,满足该图的所有边都有至少一个顶点在这个点集中,点集大小最小的成为最小点覆盖

所以最小点覆盖集也就是要找到一个最小的点集(每选择一个点就相当于选择了所有以此为一个端点的边),让这个点集包含所有的边并且点数最小。

最大匹配定义就是以上讲的匈牙利算法求得的好东西

先讲方法。

假设我们已经在一个二分图中求得了一个最大匹配,并且包含了m条边。

kng1.png

然后要考虑如何构造一个点覆盖集。

首先从右部点中没有被匹配的点出发,走增广路(一条非匹配边,一条匹配边...),把一路上经过的点都打上标记(包括起点)

比如在这个图中,我们就可以通过右边没有被匹配的点5出发,依次经过5,2,4,0,6并把他们全部打上标记如下。

kng2.png

完成了打标记的操作之后,我们只需要选取左部被标记的点与右部没有被标记的点,就组成了一个点覆盖集且是最小点覆盖集。

kng3.png

不仅如此,它还刚好选中了m个点。

为什么呢?

先来看看在我们这个标记的规则下,增广路有哪些奇怪的性质:

对于每条我们经过了的增广路$(u,v)$,两边的$u,v$必定都被标记了(确实必定),然后我们以边的走向分为两部分。

1.从左部点走向右部点

2.从右部点走向左部点

首先,为什么这么选择下来就是一个点覆盖集?

首先,我们先试探着选择左部被标记的点

对于在经过的增广路径上的点,很明显可以通过选出其中左部端点囊括这一部分。(即选取左部被标记了的点)

然后,对于不在增广路上并且在选取了左部标记点后没有被覆盖的边,它所连接的右部点一定是没有被标记的。

为什么?

假设有这样一条神奇的边$(u,v)$,其中$v$被标记,而$u$没有。

如果这条边是匹配边,那么$v$的标记一定是从$u$经过得到的,那么$u$应该被标记,矛盾。

如果这条边是非匹配边,$v$的标记来自于另一条匹配边,按照增广路的定义,还可以继续走向$u$,$u$应该被标记,矛盾。

综合,没被覆盖的边连向的右部点一定没有被标记,所以把它们选中就可以覆盖剩下的边了。

QED。

然后,为什么这么选择下来一定选中了m个点?

回顾标记过程,我们从右部没有被选中的点出发,走增广路并沿途打标记。

如果我们能在出发之后走向一个左部的点,那么这个左部的点一定还能继续走下去。也就是这个点原本有对应的匹配并且不是这个未被选中的右部点,否则该右部点会被标记

因此,被选中的左部点的个数=经过的匹配边数

接下来再看右部点。

每一条没有被覆盖并且不在增广路上的边,连向的右部点一定是没有被选中的。(同上)

所以只需要选择这些没有被选中的右部点,就囊括了这些边。

因为每个没有被选中的右部点,连且仅连向一条匹配边,所以未被选中的右部点的个数=剩余的匹配边数

两者相加,刚好就是匹配边的数量。

QED。

最后,为什么这么选择下来一定是最小的点覆盖?

覆盖m条匹配边至少需要m个点。

QED。

于是这个定理就被感性证明了。


p.s. 以下结论只粗略进行以下感性理解,具体证明下次也不一定更新

最大点独立集=总点数-最大匹配边数

最大点独立集:在二分图中,选最多的点,使得任意两个点之间没有直接边连接。

由以上证明可知,最大匹配边数=最小点覆盖集。

而最大点独立集只需要我们从所有的点中,把最小点覆盖集中的点全部删去,所剩下的点就一条边都不剩了,所以它们当然是点独立集。至于为啥最大,不想写了

另:最小边覆盖(选择最小的边覆盖所有的点)=最大点独立集


题目&代码 讲解有空一定更

ZOJ-1140

代码:Courses 课程.cpp

ZOJ-1364

Zju1364 Machine Schedule.cpp

留言:2020.5.30 题目下次一定更新

(题目下次一定更新)

最后修改:2020 年 05 月 30 日 10 : 56 AM