必威体育Betway必威体育官网
当前位置:首页 > IT技术

【代码实现】匈牙利算法

时间:2019-10-26 01:12:15来源:IT技术作者:seo实验室小编阅读:83次「手机版」
 

匈牙利算法

之前讲了导弹时,dalao(CJJ)把匈牙利也讲解了,我怕有些人不是很懂,我也来讲解一下。

我们正经点,不要像“剩男剩女的大潮”之类的

我还是按照dalao(CJJ)的讲法,“交朋友”

假设有AB两种人,A种人只会和B种人交朋友,B种人也只会和A种人交朋友,且只会跟较好的人交朋友,现在,主动权在A种人,如图:

一张非常复杂的人际关系

(左边是A种人,右边是B种人)

1

1来交朋友,第一个备选朋友是一,因为一还没有交朋友,所以他俩就成了。

成了一对!

2

2来交朋友,第一个备选朋友是二,以为二还没有交朋友,所以他俩也成了。

两对了

3

3来交朋友,第一个是备选朋友一,因为一已经与1交朋友了,所以把他俩“擦”掉,然后3与一交朋友。

有人可能会被套麻袋[笑]

4

因为上一个操作,所以1没了朋友,那么这一轮给他找一个朋友,我们看到,1的第二个备选朋友是二,但是二已经是2的朋友了,所以再次把他俩“擦”掉,然后让二与1交朋友

很好,要打架了!

5

又是因为上一个操作,所以2没了朋友,那么这一轮给他找一个朋友,2的第二个备选朋友是三,现在三没有朋友,所以让2与三交朋友

终于平息了~

6

现在让4交朋友,他的第一个备选朋友是三,但是三与2已经是朋友了,理所当然,把他俩“擦”掉,让三与4交朋友

2现在暴跳如雷!

7

现在2已经是去掉了两个朋友,现在是为2找朋友,他的第三个备选朋友是四,这次好了,终于交完朋友了!

终于搞好了!

这就是匈牙利算法

就是一个个交朋友,一个个拆朋友。

代码实现呢,有时间我会写写,

不过导弹使用了匈牙利算法,可以看一下

导弹


一天后……

这是代码实现

记得在mainmainmain里面调用HungarianHungarianHungarian时先把flogflogflog清为000,HungarianHungarianHungarian函数里就不用清了

bool Hungarian(int k)//k是本轮要连得点,返回是否能够连接 
{
	int t=0;
	for(int i=h[k];i;i=wh[i].t)//枚举连接的点(用的是邻接表存)
	{
		if(!flog[wh[i].y])//如果它没有被其他点连过 
		{
			t=hw[wh[i].y];//先记录一下,防止出现差错 
			hw[wh[i].y]=k;//这一个点被k点连了
			flog[wh[i].y]=1;//这一个点被连过了
			if(!t || Hungarian(t))return 1;
			//如果这个点之前没有被连过,
			//或着是之前连这个点的点还可以连其他点
			//那么直接退出代表k点可以连 
			hw[wh[i].y]=t;//如果不可以连就把值赋回去
		}
	}
	return 0;//退出代表不能连 
}

文章最后发布于: 2019-01-25 12:09:08

相关阅读

快速求平方根算法

  对于一个整数求解其平方根可以使用“二分法”和“牛顿法”。二分法算法:给定精确度ξ,用二分法求函数f(x)零点近似值的步骤如下

算法讲解:二分图匹配【图论】

二分图匹配,自然要先从定义入手,那么二分图是什么呢? 二分图: 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如

对称与非对称加密算法

一、对称加密算法     指加密和解密使用相同密钥的加密算法。对称加密算法用来对敏感数据等信息进行加密,常用的算法包括DES、

启发式算法

链接:https://www.jianshu.com/p/e2aec624106a 什么是启发式算法 启发式算法一般用于解决NP-hard问题,其中NP是指非确定性多项式。

【图像算法】DDE

1)什么是DDEFLIR systems研发出一种强大的算法,帮助用户解决在高动态范围场景中丁威迪对比度目标的难题。此算法称为 数字图像细

分享到:

栏目导航

推荐阅读

热门阅读