二分图匹配,匈牙利算法原理与实现 - 几何思维

Chase620 等级 650 0 0

文章首先于微信公众号:几何思维,关注第一时间获取更新信息

以下场景太过真实,但都是虚构,为了讲清楚理论的过程。如有雷同,纯属我瞎编,还望勿对号入座。

1 婚恋市场,明码实价

中国如今男女比例严重失衡,2021年预计将有9200万单身贵族。为了帮助解决这个社会性问题,提升整体人民的幸福感,小K打算投身到这份伟大的事业中。
几何思维”婚恋所,用最科学的方法,帮你脱单。通过概率论寻找最佳匹配对象,再通过微积分精确计算好感上升曲线,最后用数值分析无限逼近对方的理想型。最可怕的是,还包邮呢亲,关注一波了解一下?

上班第一天,老板给了小K一份单身男女好感的数据资料。如下图,连线表示双方互有好感,可以尝试处对象。

二分图匹配,匈牙利算法原理与实现 - 几何思维

突然遇到了一个问题,那怎么才能进行最大的匹配,创造整体人民最大的幸福感呢,当然也可以顺便拿最多的中介费啦。

2 不要怂,就是干

很多时候不是你比别人差,而是你执行力不够,在犹豫中丧失机会。
大家就先行动起来吧。

快看,男1号选手在小K的鼓励(怂恿)下,率先对女1号发起了进攻。在离失败只有0.01公分的时候,他竟然奇迹般的完成反杀,没错,他成功啦,这种高超的技巧,娴熟的手法简直如同教科书一般,值得在座的每个同学深入研究反复琢磨啊。

二分图匹配,匈牙利算法原理与实现 - 几何思维

男2号选手也不甘落后,也对女2号选手发起了进攻,没错,又一次成功啦。

二分图匹配,匈牙利算法原理与实现 - 几何思维

男3号选手:我勒个去,我上我也行啊。于是也对自己心动的女1号发起了进攻,毫无意外,他阵亡了。。。

二分图匹配,匈牙利算法原理与实现 - 几何思维

中间彩蛋。

二分图匹配,匈牙利算法原理与实现 - 几何思维

男3号不甘心,原地复活,想再战一回。在一个地方跌倒,咱们就换一个地方再跌。。。
于是对女2号发起了进攻。

二分图匹配,匈牙利算法原理与实现 - 几何思维

几经波折。

二分图匹配,匈牙利算法原理与实现 - 几何思维

男3号终于也成为了有牵绊的男人,不论未来有多久,只在乎曾经拥有过。

二分图匹配,匈牙利算法原理与实现 - 几何思维

男4一看:这也没我啥事儿了啊。

以上的过程其实就是经典的匈牙利算法,求解二分图的最大匹配问题。

3 匈牙利算法

二分图
定义:设G=(V,E)是一个无向图,顶点集V可分割为两个互不相交的子集X,Y,并且图中每条边关联的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

二分图匹配,匈牙利算法原理与实现 - 几何思维

判断是否为二分图的充要条件:G至少有两个顶点,且其所有回路的长度均为偶数。
判断方法:染色法

  • 开始对任意一未染色的顶点染色
  • 判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色;
  • 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图,若颜色不同则继续判断

可用bfs或者dfs。

二分图匹配,匈牙利算法原理与实现 - 几何思维

匹配
在二分图G的子图M中,M的边集E中的任意两条边都不依附于同一个顶点,则称M是一个匹配

二分图匹配,匈牙利算法原理与实现 - 几何思维

饱和点
匹配M的边集所关联的点为饱和点,否则为非饱和点。如上图:

  • \(M_1\)的饱和点:\(X_1,X_3,X_4,Y_1,Y_2,Y_3\)。
  • \(M_2\)的饱和点:\(X_1,X_2,Y_1,Y_3\)。

交错路
定义:图G的一条路径,且路径中的边在属于M和不属于M中交替出现。

二分图匹配,匈牙利算法原理与实现 - 几何思维

增广路(非网络流中的定义)
定义:一条交错路,且该交错路的起点和终点都为匹配M的非饱和点。
如上图,交错路1是增广路;交错路2不是增广路,因为终点$$X_1$$不是非饱和点。

由增广路推出以下结论:

  • 路径的边数为奇数,第一条边和最后一条边都不属于M
  • 将路径中的边的匹配方式取反操作,会得到更大的匹配M',匹配数加1
  • M为图G的最大匹配等价于不存在M的增广路

二分图匹配,匈牙利算法原理与实现 - 几何思维

匈牙利算法核心思想:

  • 1.初始匹配M为空
  • 2.找出一条增广路径p,取反操作得到更大的匹配M'代替M
  • 3.重复步骤2,直到找不出增广路为止

4 代码实现

变量定义及初始化

const int MAXM = 200, MAXN = 200;
bool map[MAXN][MAXM] = {false}, visit[MAXM];
int n, m, x[MAXM], y[MAXN], ans = 0; 

初始化

void init() {
    memset(x, 0xff, MAXM * 4);
    memset(y, 0xff, MAXN * 4);
    memset(map, false, MAXN * MAXM);

    int num, temp;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> num;
        for (int j = 0; j < num; ++j) {
            cin >> temp;
            map[i][temp - 1] = true;
        }
    }
} 

递归寻找增广路

bool hungary(int u) {
    for (int i = 0; i < m; ++i) {
        if (!visit[i] && map[u][i]) {
            visit[i] = true;
            if (y[i] == -1 || hungary(y[i])) {
                x[u] = i;
                y[i] = u;
                return true;
            }
        }
    }
    return false;
} 

遍历所有点

int main() {
    init();
    for (int i = 0; i < n; ++i) {
        if (x[i] == -1) {
            memset(visit, false, MAXM);
            if (hungary(i)) {
                ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
} 

测试数据

输入
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
输出
4 

扫描下方二维码关注公众号,第一时间获取更新信息!

二分图匹配,匈牙利算法原理与实现 - 几何思维

本文转自 https://www.cnblogs.com/kylewilson/p/14517884.html,如有侵权,请联系删除。

收藏
评论区

相关推荐

Java核心技术 之安装环境 踏出第一步
Java JDK安装与配置 1、下载 官网地址:http://www.oracle.com/technetwork/java/javase/downloads/index.html (1)点击DOWNLOAD 这里写图片描述(https://imghelloworld.osscnbeijing.aliyuncs.com/4
讲解Excel中16种图表类型的“含义”,这次该知道怎么画图了!
(https://imghelloworld.osscnbeijing.aliyuncs.com/d61464c6ae6fdb4aba5501534164e09c.png) 大家都知道,相同的数据,使用不同的图表进行体现,效果也会千差万别,那么我们应该如何正确选择,才能让图表的作用发挥到极致呢? 1.柱形图
python数据分析与可视化——利用Seaborn进行绘图
利用Seaborn进行绘图下面例子中所用数据下载地址——Matplotlib绘图基本模仿MATLAB绘图库,其绘图风格和MATLAB类似。由于MATLAB绘图风格偏古典,因此,Python开源社区开发了Seabo
非常实用的GitHub项目
CoilCoil是Android上的一个全新的图片加载框架,它的全名叫做 coroutine image loader,即协程图片加载库。与传统的图片加载库Glide,Picasso或Fresco等相比。该具有轻量(只有大约1500个方法)、快、易于使用、更现代的API等优势。它支持GIF和SVG,并且可以执行四个默认转换:模糊,圆形裁剪,灰度和圆角。示例如
Android-图片加载库Coil使用教程
框架介绍Coil是Android上的一个全新的图片加载框架,它的全名叫做coroutine image loader,即协程图片加载库。与传统的图片加载库Glide,Picasso或Fresco等相比。该具有轻量(只有大约1500个方法)、快、易于使用、更现代的API等优势。它支持GIF和SVG,并且可以执行四个默认转换:模糊,圆形裁剪,灰度和圆角。
讲解Excel的16种图表类型的“含义”,知道该怎么画图了!
大家好,我是小五🐶 相同的数据,使用不同的图表进行体现,效果也会千差万别,那么我们应该如何正确选择,才能让图表的作用发挥到极致呢? 1.柱形图 柱形图是最常见的图表类型,它的适用场合是二维数据集(每个数据点包括两个值,即X和Y),但只有一个维度需要比较的情况。例如,如下图所示的柱形图就表示了一组二维数据,【年份】和【销售额】就是它的两个维度,但只需要比
Pytorch构建栈式自编码器实现以图搜图任务(以cifar10做数据集)
(Pytorch构建栈式自编码器实现以图搜图任务) 本文旨在使用CIFAR10数据集,构建与训练栈式自编码器,提取数据集中图像的特征;基于所提取的特征完成CIFAR10中任意图像的检索任务并展示效果。 搞清楚pytorch与tensorflow区别 pytorchpytorch是一种python科学计算框架作用: 无缝替换numpy,通过G
图像中查找小图像的方法
如果有一副大图像和该大图像中截取的部分小图像,用人眼很容易找到小图像在大图像中的位置,但如果想通过电脑自动查找怎么解决呢?有2种方法,一种是直接通过图像矩阵的数据内容匹配进行查找,在一个大矩阵中查找对应小矩阵,这是精确匹配,要求小矩阵的所有元素与大矩阵中某部分的所有元素完全一致;另外一种就是OpenCVPython的HMT(hitandmiss transf
PyQt转换显示Python-OpenCV图像实现图形化界面的视频播放
一、引言在PythonOpenCV中显示图像时调用的是一个单独的窗口,有时我们需要将这些图像显示在PyQt的图形化界面上,这样就可以将整个图像显示与PyQt图形化界面进行整合。但OpenCV格式的图像和PyQt格式的图像并不同,这就需要进行转换。二、背景知识1. PythonOpenCV的图像是BGR格式的,而PyQt图像格式是RGB格式的,二者需要转换;
面试字节我被String类的问题给问死了!
"+" 是怎么连接字符串的?(JDK1.7及以上)总结:使用 "+" 连接字符串时,实际上是使用临时创建的StringBuilder对象来辅助完成的。对于编译时常量,在编译后直接计算出字符串的值,而不会在运行时创建临时的StringBuilder对象来完成字符串连接。在循环中对String对象进行连接,应该直接使用StringBuilder代替 "+",这样
数据可视化干货:使用pandas和seaborn制作炫酷图表
吾日三省吾身:为人谋而不忠乎?与朋友交而不信乎?传不习乎?导读: 我们介绍过用matplotlib制作图表的一些tips,感兴趣的同学可以戳→。matplotlib是一个相当底层的工具。你可以从其基本组件中组装一个图表:数据显示(即绘图的类型:线、条、框、散点图、轮廓等)、图例、标题、刻度标记和其他注释。 在pandas中,我们可能有多个数据列,并且带有行
刷爆全网的动态条形图,原来5行Python代码就能实现!
说起动态图表,最火的莫过于动态条形图了。 在B站上搜索「数据可视化」这个关键词,可以看到很多与动态条形图相关的视频。 好多视频都达到了上百万的播放量,属实厉害。 目前网上实现动态条形图现成的工具也很多。 比如数可视的「花火hanabi」,嫡数的「镝数图表」,以及国外网站「Flourish」。 但是作为一名Pythoner,当然是想要研究一下如何
Python爬虫 | 批量爬取今日头条街拍美图
专栏作者:霖hero,在职爬虫工程师,熟悉JS逆向与分布式爬虫。喜欢钻研,热爱学习,乐于分享。公众号后台回复入群,拉你进技术群与大佬们近距离交流。 01前言 大家好,我是J哥🚀在以前的文章中我们学了Ajax数据爬取,这篇文章我们以今日头条为例,通过分析Ajax请求来抓取今日头条的街拍美图,并将图片下载到本地保存下来。准备好没,我们现在开始! 0
PySimpleGUI 进阶| 原来用Python做一个图片查看系统,还能这么简单!
大家好,在我们已经介绍了为什么以及如何基本使用PySimpleGUI,并且对一些比较常用的元素(element)也有所了解。 本文将对基础版中的一些元素与新讲解的元素进行组合,构建一个图片查看系统与一个简易的计算机视觉系统(代码调用前置照相机)作为PySimpleGUI的进阶篇,我将分为以下两个部分讲解: 图片查看系统的构建 简易计算机视觉
“挂图作战”与地理空间的“相生”关系
在传统的地理空间,地图作为描绘地理现象的重要载体,自古以来就是指挥作战不可或缺的工具;如今在网络空间,也迫切需要能够全面展示网络空间信息的网络空间地图,从而建立起网络空间与地理空间的关联。依托网络安全态势感知平台,将网络空间地图与平台智慧大脑有机结合,实现网络空间的“挂图作战”。网络空间具有高度的复杂性,并与地理空间高度关联,共同构成了人类活动的现实空间。要