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

Chase620 等级 945 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,如有侵权,请联系删除。

收藏
评论区

相关推荐

Pytorch构建栈式自编码器实现以图搜图任务(以cifar10做数据集)
(Pytorch构建栈式自编码器实现以图搜图任务) 本文旨在使用CIFAR10数据集,构建与训练栈式自编码器,提取数据集中图像的特征;基于所提取的特征完成CIFAR10中任意图像的检索任务并展示效果。 搞清楚pytorch与tensorflow区别 pytorchpytorch是一种python科学计算框架作用: 无缝替换numpy,通过G
FPGA+CPU助力数据中心实现图像处理应用体验与服务成本新平衡
![](https://oscimg.oschina.net/oscnet/b27bc0d4a279e71e209ef9a9520ee00c145.jpg) > 图片逐渐成为互联网主要的内容构成,相应的图片处理需求也在高速成长,移动应用与用户生产内容(UGC)正在驱动数据中心图像处理的业务负载快速增加。 本文深维科技联合创始人兼CEO樊平详细剖析了
Java Web Day3
本节内容 1.浏览器与服务器交互图 2.JavaWeb项目的组织结构 3.HTTP协议 一、浏览器与服务器交互图 ![](https://oscimg.oschina.net/oscnet/fb4840168c2ce0bd70f10bcc95ba27793ed.png) 二、web项目的组织结构   ![](https://oscimg.osc
ThinkPHP+Uploadify图片上传预览与缩略
控制文件内容: public function uploadimages(){         $date = date('Ymd');         $targetFolder = '../Uploads/'.$date.'/'; // Relative to the root         if(I('action'
14、OpenCV实现图像的空间滤波——图像锐化及边缘检测
1、图像锐化理论基础 ========== 1、锐化的概念 -------     图像锐化的目的是使模糊的图像变得清晰起来,主要用于增强图像的灰度跳变部分,这一点与图像平滑对灰度跳变的抑制正好相反。而且从算子可以看出来,平滑是基于对图像领域的加权求和或者说积分运算的,而锐化则是通过其逆运算导数(梯度)或者说有限差分来实现的。 2、图像的一阶微分和二阶
Android OpenCV(二十二):边缘检测
边缘检测 ---- > 什么是图像的边缘? > > 图像的边缘是图像最基本的特征之一。所谓边缘(或边沿)是指周围像素灰度有跳跃性变化或“屋顶”变化的那些像素的集合。边缘是图像局部强度变化最明显的地方,它主要存在于目标与目标、目标与背景、区域与区域之间,因此它是图像分割依赖的重要特征。从本质上说,图像边缘是图像局部特性不连续性(灰度突变、颜色突变、纹理结构
C#与sql进行图片存取
1 using System; 2 using System.Collections.Generic; 3 using System.ComponentModel; 4 using System.Data; 5 using System.Drawing; 6 using System.Linq; 7 using System.Text; 8 usin
Django与drf 源码视图解析
0902自我总结 ======== Django 与drf 源码视图解析 ================== 一.原生Django CBV 源码分析:View ------------------------ """ 1)as_view()是入口,得到view函数地址 2)请求来了调用view函数,内部调用dispatch函数
Element upload组件上传图片与回显图片
场景:新增商品时需要添加商品主图,新增成功之后可编辑 上传图片: <el-form-item label="专区logo:" style="height:160px"> <div class="img"> <el-upload action
G6 v3.5:全新节点分组与图算法
![](https://oscimg.oschina.net/oscnet/up-83f0369d1b0799f08d1ee81bde9e03bbeaa.JPEG) [AntV G6](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fgithub.com%2Fantvis%2FG6) 是一
G6:AntV 的图可视化与图分析
![](https://pic1.zhimg.com/v2-de9f0f46f75755ef43373a1ee0e0e2cf_1200x500.jpg) 导读 -- G6 是 AntV 旗下的一款专业级图可视化引擎,它在高定制能力的基础上,提供简单、易用的接口以及一系列设计优雅的图可视化解决方案,是阿里经济体图可视化与图分析的基础设施。今年 AntV 1
Native地图与Web融合技术的应用与实践
![](https://oscimg.oschina.net/oscnet/up-aad2c4fa385750c08df2ae9ab139e03c96b.JPEG) 1\. 背景 ------ 美团打车业务很早就在美团App与点评App中提供了服务入口,并在技术上采用了H5与Native的混合开发技术。随着业务上线,有用户反馈我们的地图性能有一些问题,原
OpenLayer4与mapV结合蜂巢图效果
在这里mapV是一款数据可视化的软件,数据的展示的效果灰常炫酷,但是问题来了,mapV是百度出的,是基于百度地图api做的,百度地图api是不开源的,说到是不是感觉很绝望,如果想做到mapV和OpenLayer结合,我们可以超图的一款api基于openlayer开发的api,刚好该api也结合mapV,我们可以间接结合二者。 来张图: ![](https
Python数据结构与算法——图
### 图的定义 ![](https://oscimg.oschina.net/oscnet/up-f5b4e14079290acba3893a5c5cb1585ca01.png) 图(graph) 是由一些点(vertex) 和这些点之间的连线(edge) 所组成的;其中,点通常称为顶点(vertex),而点到点之间的连线通常称之为边或者弧(edge)
Swoft 图片上传与处理
**上传** 在Swoft下通过 \Swoft\Http\Message\Server\Request -> getUploadedFiles()['image'] 方法可以获取到一个 Swoft\\Http\\Message\\Upload\\UploadedFile 对象或者对象数组(取决于上传时字段是image还是image\[\])