【代码实现】匈牙利算法

　

匈牙利算法

之前讲了导弹时，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交朋友

7

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

这就是匈牙利算法。

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

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

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

导弹

---

一天后……

这是代码实现

记得在$main$main里面调用$Hungarian$Hungarian时先把$flog$flog清为$0$0，$Hungarian$Hungarian函数里就不用清了

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研发出一种强大的算法，帮助用户解决在高动态范围场景中丁威迪对比度目标的难题。此算法称为 数字图像细