文档章节

二分图匹配之匈牙利算法(超级详细,看完不懂都难)

o
 osc_fmg49rzg
发布于 2019/03/20 11:31
字数 1040
阅读 13
收藏 0

精选30+云产品,助力企业轻松上云!>>>

最近刚学了二分图匹配,发篇博客分享一下。

 


 

 

要了解二分图匹配首先要知道二分图是什么:

 

  “设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。” 

  摘自百度百科

 

用人话来说就是把一个图中的点分成两个集合,然后一个集合中的点只能和另一个集合中的点连边,这样的一个图就是二分图。

 

不要嫌烦,我们再来看看一些相关名词:

 

匹配:再图中选择若干个边,任意两个边没有公共顶点。

最大匹配:最大的匹配方案。

 

那么什么是二分图匹配呢?顾名思义就是在一个二分图中寻找他的最大匹配。

 


 

 

知道了二分图匹配的定义,我们接下来用一个生(wu)动(liao)的例子来理解二分图匹配的应用以及算法流程:

 

在遥远的未来,拥有世界上大部分财富的人同时拥有了这世界上大部分的女人,这导致大部分正常男人根本就没有伴侣。

政府为了解决这个问题,取消了原有的婚姻制度,取而代之的是一个强制性的婚姻制度。在这个婚姻制度中,一旦年龄超过18岁,公民便会被强制匹配一个伴侣,必须与其共度余生。而政府为了公民的婚姻更加和谐,会事先评估每个人的性格,然后尽可能将性格合适的匹配在一块。然而不一定能让所以人都找到性格合适的伴侣,这时就需要“逼婚员”的努力,让大家的婚姻尽可能的和谐。

 

逼婚员今天的任务可以用下面这张丑陋的图表示:

(方形点表示男生,椭圆点表示女生,边表示他们性格合适)

逼婚员都收过专业的训练,他们匹配都有特殊的方法。

让我们看看逼婚员怎么处理今天的任务吧。首先他把男生A和女生A匹配在了一块。

 

然后同时又看到男生B和女生A也匹配,而且男生A除了和女生A匹配,还和女生B匹配,于是就把女生B匹配给了男生A,女生A匹配给男生B。

 

 

 剩下三个直接匹配就完事了。。。

 

 


 

 通过上面的例子可以看到匈牙利算法的思想非常暴力,就是对于个边,能连就直接连,不能连就尝试让之前的点给当前点腾出来一个点。

 

现在我们来看看代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, m, e, ans = 0,
link[N]; bool vis[N];//link[v]表示v连向的点, vis表示某个点是否被访问过。
vector<int> g[4*N];//vector存图
//快读
inline int read() {
       register int x = 0, t = 1; register char ch = getchar();
       while ((ch < '0' || ch > '9') && ch != '-')ch = getchar();
       if (ch=='-') { t = -1; ch = getchar(); }
       while (ch >= '0' && ch <= '9'){ x = (x<<3) + (x<<1) + (ch^48); ch = getchar(); }
       return x*t;
}
//算法核心
bool dfs(int x) {
	for (int i = 0; i < g[x].size(); i++) {
		int v = g[x][i];
                //如果没被访问
		if (!vis[v]) {
			vis[v] = 1;
			if (link[v] == -1 || dfs(link[v])) { //若是v还没有被配对,就把v配对给x,否则让link[v]腾出v给它。
				link[v] = x; //把v连接到x
				return 1; //表示x能配对到点
			}
		}
	} return 0; //x不能配对到点
}

int main() {
	memset(link, -1, sizeof(link));
	n = read(), m = read(), e = read();
	for (int i = 1; i <= e; i++) {
		int u = read(), v = read();
		if (u > n || v > m || u < 1 || v < 1) continue;
		g[u].push_back(v+n); //建边,注意一定要是单向边
	} for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		if (dfs(i)) ans++; //如果能匹配到答案加一
	} cout << ans;
	return 0;
}

  

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
2016级算法期末上机-H.难题·AlvinZH's Fight with DDLs III

1119 AlvinZH's Fight with DDLs III 思路 难题,最小点覆盖。 分析题意,某一个任务,既可以在笔记本A的 $a$ 模式下完成,也可以在笔记本B的 $b$ 模式下完成。如果笔记本A处于x模式,那么所...

osc_dh0xu7zu
2018/01/07
1
0
【网络流相关】二分图匹配

Luogu P3386 首先看看二分图的定义: 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的...

woshiren
04/30
1
0
网络流之二分图匹配【转】

原文链接:https://blog.csdn.net/sunny_hun/article/details/80627351 二分图:  二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子...

osc_vg6s3gcq
2018/07/17
1
0
【原创】我的KM算法详解

0.二分图 二分图的概念 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V, E)是一个无向图。如果顶点集V可分割为两个互不相交的子集X和Y,并且图中每条边连接的两个顶点一个在X中,另一...

伊甸一点
2017/07/21
0
0
二分图算法模板以及相关知识

说说二分图,其实图论的题难点不在用算法,难在如何建图,只有图建好了,剩下的就简单了,在这说说求二分图的算法,即匈牙利算法,其实一点都不难,也很好理解拿笔写写就行了. //板子, 直接套就行 //...

Anxdada
2017/06/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如果你失明了,你怎么编程? - How can you program if you're blind?

问题: Sight is one of the senses most programmers take for granted. 视觉是大多数程序员认为理所当然的感官之一。 Most programmers would spend hours looking at a computer monitor......

技术盛宴
54分钟前
16
0
如何删除使用Python的easy_install安装的软件包? - How do I remove packages installed with Python's easy_install?

问题: Python's easy_install makes installing new packages extremely convenient. Python的easy_install使安装新包非常方便。 However, as far as I can tell, it doesn't implement th......

fyin1314
今天
11
0
如何将逗号分隔的字符串转换为数组? - How to convert a comma separated string to an array?

问题: I have a comma separated string that I want to convert into an array, so I can loop through it. 我有一个逗号分隔的字符串,我想将其转换成数组,因此可以循环遍历它。 Is the...

富含淀粉
今天
13
0
深源恒际:担心个人身份被冒用?不存在!

本文作者:c****t 近日,苟晶被冒名顶替身份参加高考的事件在社会各界掀起广泛热议。事件调查结果公布后,舆论风向逆转,吃瓜群众认为当事人夸大其词消费了公众情绪,一边对当事人所遭遇的不...

百度开发者中心
昨天
5
0
CKEditor 5 + SpringBoot实战(三):SpringData JPA数据持久化

在本系列的文章中,我将介绍如何在Spring Boot Application中使用CKEditor编辑器。介绍的内容包括基本环境的搭建,文件上传,SpringData JPA数据持久化,CKEditor5的安装,CKEditor图片上传,...

树下魅狐
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部