RikkaJ_Blog RikkaJ_Blog

[学习笔记]二分图匹配问题

in 学习笔记 read (269) 文章转载请注明来源!

二分图最大匹配问题

学习时间 4月23日


学习需知

首先我们学习二分图最大匹配问题需要三个前提

  • 了解什么是图,并且了解对图的有关操作
  • 函数的理解,与递归代码阅读能力
  • 动脑子,学习之后自行A掉例题

问题

(以下所有内容均为博主的理解,如果与官方理解有冲突,请谅解)
阅读前请记住三个问题:

  1. 什么是二分图?
  2. 如何匹配,匹配的思想是怎样的?
  3. 二分图最大匹配适用于哪些题目?

概述

有小伙伴这么问:我现在基础学(刘汝佳的紫皮前四章)完了,会了函数与递归,想学图论,但又只会存图,我该从哪个方面开始接触图论呢?
当然是二分图匹配辣~ 几需体验三番钟你就会了解这个船新算法。
好了 撤回正题——

什么是二分图匹配?

其实.. 我也不知道... 咳咳咳,在我的理解里面,二分图的意思是,可以将一个图分割成两个,并且在同一个图里面,所有的点都没有直接或者间接的联系,我们就可以将这种图称之为二分图。那么匹配是什么意思呢,就是说在我说分割的其中一个图的其中的点是与另外一个分割的图的其中某一些点是有联系的,我们将其连线(存图),就完成了我们的匹配操作。

什么是二分图最大匹配?

那么最大匹配的意思就是说,我们在这种匹配的众多操作中选取一个能匹配的点最多的一种操作,而这种操作就是我们想要得到的二分图最大匹配。

那我想看看二分图长什么样子可以吗?

当然没问题,如下图所示

请输入图片描述

思想论述

对于一个算法的分析最好是针对一道例题来解释,这里脑补了一道例题,如下

一天,Rikka酱和几个老男人准备去看《头号玩家》(肉...团[雾]),但是走到电影院门口却突然觉得几个大男人看电影太孤单寂寞了,于是准备找几个漂亮的小姐姐一起看,大家都掏出了手机,准备打给自己心里的另一半,但是不是每个小姐姐都愿意和其看电影,小姐姐必须对其有好感,才会答应一起去看电影,为了让各位老男人都能满足自己的(性欲[雾])心情,Rikka酱准备帮助他们,让他们最大限度的与小姐姐成对去看电影,求最多能够让多少个老男人与小姐姐成对去看电影?

首先我们来分析这道题,因为老男人不可能邀请老男人来看电影(雾),小姐姐与小姐姐间也不可能存在相互邀请的关系(雾),于是我们就可以建出两个图内所有元素点毫无关联的图,因为邀请的小姐姐必须对于打电话的老男人有好感,所以我们可以将其连接起来,表示这对男女是可以一起相伴去看电影的,反之则会被小姐姐拒绝。
处理完图之后,我们就已经完成了二分图匹配了(匹配就是老男人与小姐姐中间连接的线)
然后我们就考虑二分图最大匹配了,想要最大匹配,我们就要从第一个老男人开始枚举,如果他拨打电话的小姐姐没有被邀请,并且对他有好感,那么就可以匹配在一起,如果他所拨打电话的小姐姐被邀请了,那么看看这个小姐姐所匹配的老男人是否还有其他的人选可以选择,如果有那么就选择另外一个小姐姐,将这个小姐姐让给另外一个老男人(老男人果然都是讲义气的),自己则邀请另外那个小姐姐---此操作看起来就是一个递归的写法,实际也的确是一个递归的写法。
那么就讲完了,最后来看代码吧!

核心代码 邻接表和匈牙利算法

void addedge(int x,int y)
{
    ver[tot++] = y;
    to[tot] = head[x];
    head[x] = tot; 
}

bool can(int x)
{
    for (int i=head[x];i;i=to[i])
    {
        int y = ver[i];
        if(!Vis[y])
        {
            Vis[y] = 1;
            if(!curch[y]||can(curch[y]))
            {
                curch[y] = x;
                return 1;
            }
        } } return 0;
}

核心代码 邻接矩阵和匈牙利算法

int Map[MAX_N][MAX_N]; //Map[i][j]表示下标为j的小姐姐对下标为i的老男人有好感
bool can(int x)
{
    for (int i=1;i<=m;i++) //m表示小姐姐的数量
    {
        if(!Vis[i])
        {
            Vis[i] = 1;
            if(!curch[i]||can(curch[i]))
            {
                curch[i] = x;
                return 1;
            }
        } } return 0;
}

推荐题目:

棋盘覆盖
多米诺骨牌
寻找代表元

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

本文基于《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
文章链接:http://rikkaj.com/index.php/archives/8/ (转载时请注明本文出处及文章链接)

学习笔记
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by YoDu
前篇 后篇
雷姆
拉姆