【图论】浅谈二分图匹配【匈牙利算法】

发布于:2023-01-23 ⋅ 阅读:(630) ⋅ 点赞:(0)

首先,什么是二分图?

百度百科:

​ 二分图又称作二部图,是图论中的一种特殊模型

​ 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),

​ 并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),

​ 则称图G为一个二分图。

人话:

​ 有一破图,给他分了,

​ 分成两半,俩破图,

​ 俩破图里点与点不相连

​ 如果有边,一定是一个破图的点连向另外一个破图的点。

亘古不变的比喻:

​ 有男嘉宾与女嘉宾参加《非洲勿扰》,

​ 他们都不是同性恋,所以不会喜欢同性

​ 有一些男女嘉宾互有好感,但毕竟是相亲,可能一个人与多个人互有好感


二分图匹配

让最多的男嘉宾牵手,注意和谐社会一夫一妻

网络流

天 书

匈牙利算法

上帝拯救蒟蒻,发明了匈牙利算法!

原理简介:

趣写算法系列之--匈牙利算法_Dark_Scope的博客-CSDN博客_匈牙利算法

模板:搭配飞行员

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,

这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。

由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,

问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

模板题,不解释

int choose(int x)
{
	for(int i=m+1;i<=n;i++)
	{
		if(a[x][i]==0 || vis[i]==1)continue;
		vis[i]=1; 
		if(c[i] == 0 || choose(c[i]))
		{
			c[i]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	for(int i=1;i<=m;i++)
	{
		memset(vis,0,sizeof(vis));
		if(choose(i))ans++;
	}
}

我太弱了,只讲了皮毛,喷!


网站公告

今日签到

点亮在社区的每一天
去签到