AcWing 861. 二分图的最大匹配

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 861. 二分图的最大匹配原题链接简单

作者：

Charles__ , 2019-10-15 13:58:09 , 所有人可见 , 阅读 20088

268

124

导读：什么是最大匹配？

要了解匈牙利算法必须先理解下面的概念：

匹配：在图论中，一个「匹配」是一个边的集合，其中任意两条边都没有公共顶点。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

下面是一些补充概念：

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

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

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。

匈牙利算法

不讲算法证明(~~我也不会~~)。

用一个转载的例子来讲解匈牙利算法的流程。

代码实现匈牙利算法

首先是存图模板

//邻接表写法，存稀疏图
int h[N],ne[N],e[N],idx;
//n1,n2分别是两个点集的点的个数
int n1,n2,m;
void add(int a , int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void init()
{
    memset(h,-1,sizeof h);
}
//存边只存一边就行了，虽然是无向图。
for(int i = 0 ; i < n1 ; i ++)
{
    int a,b;
    cin>>a>>b;
    add(a,b);
}

接下来看算法模板(c++)

//match[j]=a,表示女孩j的现有配对男友是a
int match[N];
//st[]数组我称为临时预定数组，st[j]=a表示一轮模拟匹配中，女孩j被男孩a预定了。
int st[N];

//这个函数的作用是用来判断,如果加入x来参与模拟配对,会不会使匹配数增多
int find(int x)
{
    //遍历自己喜欢的女孩
    for(int i = h[x] ; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true;//那x就预定这个女孩了
            //如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩。配对成功,更新match
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }

        }
    }
    //自己中意的全部都被预定了。配对失败。
    return false;
}

//记录最大匹配
int res = 0;
for(int i = 1; i <= n1 ;i ++)
{  
    //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
    memset(st,false,sizeof st);
    if(find(i)) 
        res++;
}

下面用一个gif动图来演示这个整个配对的递归过程：
匈牙利算法.gif

练习例题：二分图的最大匹配

AC代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];

void add(int a , int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void init()
{
    memset(h,-1,sizeof h);
}

int find(int x)
{
    //遍历自己喜欢的女孩
    for(int i = h[x] ; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true;//那x就预定这个女孩了
            //如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩。配对成功
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }

        }
    }
    //自己中意的全部都被预定了。配对失败。
    return false;
}
int main()
{
    init();
    cin>>n1>>n2>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }


    int res = 0;
    for(int i = 1; i <= n1 ;i ++)
    {  
         //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
          memset(st,false,sizeof st);
        if(find(i)) 
          res++;
    }  

    cout<<res<<endl;
}

106 评论

liuxiaocs 2022-10-14 10:34

图片：

薯莨 2022-10-14 19:49

这个gif用什么做的呢?

liuxiaocs 2022-10-14 20:19 回复了薯莨的评论

原作者用这个gif动图(匈牙利算法.gif)来演示这个整个配对的递归过程，之前图挂了，现在是补链

薯莨 2022-10-14 21:52 回复了 liuxiaocs 的评论

好的好的，谢谢

露琪亚 2023-03-15 11:12 回复了薯莨的评论

visualgo.net NUS 做的算法可视化网站，有中文支持

图灵酱 2023-11-21 09:44

好快啊o(╥﹏╥)o

HappyingCoder 11个月前

简单来说st的作用就是，避免女生j的现男友k去找备胎的时候，又去找到这个j

Mollly1216 9个月前

点了，清晰明了hhhh

acwing_16834 3个月前

明白了

lsxstart 3个月前

谢谢，明白了

CSP不过300不改名 3个月前

🐂

不与世俗纷争 3个月前

太对了！！！

GinSoda 2021-12-08 16:25

优化一点点

if(!st[j] && !noask[j]) { 
    //在这一轮递归匹配中, 还未询问过该女生是否有调整空间。只要在递归中有一个女生有调整空间，既匹配成功
    //每轮递归最多询问一次该女生。在一轮递归中，不同的男生来问同一个女生，答案是一样的）
    st[j] = true; //已经询问过该女生
    //如果女孩j有调整空间（没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩），即配对成功
    if(!match[j] || find(match[j])) {
        match[j] = x;
        return true;
    }
    else noask[j] = true; //女生j无调整空间，以后不需要再询问该女生。
    // 证明：如果find(match[j])=false, 说明女生j的预定男生的所有好感对象全都有另一半，以后这些好感对象再也不会空出来，所以该男生和女生j的预定已经锁死
}

GinSoda 2021-12-08 16:29

至于为啥需要每轮重置st，感受一下这个样例
2 2 3
1 2
1 1
2 1

有恒 2021-12-21 19:51 回复了 GinSoda 的评论

重置st是为了每次find搜索时避免重复搜索

有恒 2021-12-21 20:00 回复了有恒的评论

这个是st的作用。重置是因为对于之前的一个点它相对于他走不通，但对于当前的点并于一定，所以要在重试一下这个点对于当前的点是否可行。

大智慧的益生菌 2022-02-24 18:28 回复了 GinSoda 的评论

感谢你这一问，我一直没看到哪一行，一直在找为什么这个算法是正确的。。。

GinSoda 2022-02-24 18:54 回复了大智慧的益生菌的评论

补充一下证明：
1) 匈牙利算法中，一个有伴侣的人，无论男女，不会重新变成单身。
2) 若我们尝试给一个有对象的女生换个对象，如果成功，整个交换链条终止于一个单身女性。
由2)可知，调整对象失败则代表由该女生作为起点的生成树内已无单身女性。
由1)可知，以该女生作为起点的生成树不会凭空出现单身女性。

CyanFishhh 2022-05-12 23:17

大佬牛真正解答了我的疑惑

CyanFishhh 2022-05-12 23:17 回复了 GinSoda 的评论

例子也很正确！

hed_acwing 2022-08-17 11:46 回复了有恒的评论

爱了爱了

苏小雨 2022-11-16 02:22

那为什么不能回溯st[i] true分两种情况保留无调整空间的true st就不用每轮刷新了

AcWingYyyyyy 2023-02-02 17:02 回复了有恒的评论

我感觉重置st的作用是让每个男生都可以无障碍地进行预定操作emmm

看破不点破 2023-04-04 18:52 回复了 GinSoda 的评论

你这个证明太抽象了，我说一下我的理解，其实匈牙利算法隐藏了一个很重要的引理，就是对于每一轮的find的递归st[j]的值如果为false就表示这一轮的j的匹配不能改变了，这是因为如果中间存在st[j] = true的情况，可以分三种情况考虑1.match[j] == 0：此时表示整个匹配过程中j没被匹配，那么find返回的结果一定是true，也就表示最外层返回的结果一定是true，因为只要一层递归返回true，它的其他父层都一定能调整，所以一定可以回到第一层，最后第一层也能调整，表示第一轮匹配完成，进入下一轮，st会重置，。2.match[j] != 0 但是find(match[j]) =true，同样表示可以调整，根据上一种情况，也第一层也一定可以调整，所以这一轮的匹配也就已经结束了，所以j对应得对象在这一轮也不可能被改变了。3.match[j] != 0 但是find(match[j]) =false：这表明j虽然是在这一轮第一次出现，但是j在前几轮已经被匹配了，而且这次一想要调整她的对象还失败了，说明要么她的对象已经无法调整，要么他的对象可以调整，但是调整对象导致的别的女生需要被调整，而这些在这一轮的前几次for遍历中已经试过了（这些女生的st变为了false），结果这些女生无法被调整（不然就不会for到j了），所以无论哪种情况，都表示j匹配的对象在这一轮不能调整改变。所以总的来说，如果遍历了所有轮而最终的匹配数为k的话，那么由于每一轮男生匹配的女生在当前轮都没法调整了，而我又遍历了所有轮，所以一旦强行改变，那么最多就是匹配数+1 -1 不变（强行拆散一对导致-1，强行匹配一对导致+1），所以总匹配数<= k ；所以这种方案就是最大的匹配数了
rmk：本人也是一刷匈牙利，也没看什么相关的参考文献，纯粹是自己想了想做出的证明（应该叫说明•᷄ࡇ•᷅ ，以后有机会去看看算法导论，因为我是证明教信徒(^▽^)），所以可能算法证明的不是很严谨，甚至很可能出现一些问题，欢迎大佬指正

kkkkkkkkkkkkk 4个月前回复了 GinSoda 的评论

很好的例子！！如果不加memset(st,false,sizeof(st))的话结果会输出-1，因为在find(1)的时候st[1]被标记为了true，然后轮到find(2)的时候首先if(!st[j])这里的j==1，因为全局被标记了所以直接判断就不成立了。
ps：至于为什么样例要先输1 2再输1 1是因为链式向前星访问是以最后加的边开始的这样才会从1—1这条边开始

HappyingCoder 11个月前

个人见解：输入加边的时候，编号是有可能重复的（因为左右部分的集合是分开编号的），为什么没有影响呢？（为什么还可以像之前那样处理呢？为什么不需要 add(b,a) 呢？）

因为题目的大前提就是这个图是二分图，加的边一定是左集合的 u 与右集合的 v 相连，不会出现比如左集合中的两点连线这种情况。因此 add 方法的含义就不再是，增加图中两点之间的边了，而是增加两子图之间的边。具体而言，对于 add(a,b) 方法，含义为：加入一条左集合编号为 a 与右集合编号为 b 的连线。按照这个定义，加入一条左集合编号为 u 到右集合编号为 v 的边（即题目中输入边的定义），那就执行add(u,v)；如果你再执行 add(v,u)，意义就变成了加入一条左集合编号为 v 的点与右集合编号为 u 的点的连线，显然是错的。