匈牙利算法的复杂度是O(ve),v是点的个数,e是边的个数,匈牙利算法的关键在于寻找增广路。
那么我就先科普一下什么是增广路:
增广路主要有以下几条性质:
1.增广路经上的边数一定是奇数个
2.增广路经上的边链接的两个点一定不在同一个集合中
3.增广路径上没有重复的点
4.增广路经的起点和终点所连的边一定不在当前的匹配中。
5.可以通过翻转增广路得到更匹配
那么每次找到增广路就可以将最大匹配数+1了,然后记录新的匹配。
代码如下:
因为是深搜所以我会具体将一下算法实现的思路(毕竟dfs不是那么直观^_^)
int used[MAX];
int linker[MAX];
bool dfs ( int u )
{
for ( int i = head[u] ; ~i ; i = e[i].next )
{
int v = e[i].v;
if ( used[v] ) continue;
used[v] = 1;
if ( linker[v] == -1 || dfs ( linker[v] ) )
{
linker[v] = u;
return true;
}
}
return false;
}
int hungary ( )
{
int res = 0;
memset ( linker , -1 , sizeof ( linker ) );
for ( int i = 1 ; i <= n ; i++ )
{
memset ( used , 0 , sizeof ( used ) );
if ( dfs ( i ) ) res++;
}
return res;
}
实现方法进行讲解:
首先我们将二分图的两个集合定义为左集和右集,定义used[i]数组标记右集当中的点是否被使用,防止在查找增广路的时候,右集中的点被多次使用,linker[i]数组记录右集中点i当前匹配到的左集中的点.那么基本的定义清晰了。
1.我们的做法就是枚举左集中的点作为增广路的起点,然后查找与它之间存在边的右集中的点,最开始所有的点都没有匹配,那么直接找到了一个没有匹配到任何点的右集中的点,那么当前增广路的长度为1,直接转换,因为增广路是奇数,且两端的边为不在匹配中的边,所有翻转后的最大匹配会加1。
2.然后枚举到第二个点进行匹配,如果它也直接找到没有匹配的右集中的点那么同1,如果找到和1中初始点找到的相同的点,那么进行深搜,找到1,去找另一个能够匹配的点,也就是在深搜的过程中,利用linker数组在增广路经中加了一条当前匹配中存在的边。然后翻转的时候,是匹配的边去掉,不是匹配的边加上,匹配数+1,而且依旧满足匹配的性质。
3.直到不存在增广路的时候算法结束,因为算法的最大匹配是n,所以增广路能够查找到的次数不会超过n次,因为最大匹配不会超过n。