自动搬运

查看原文

来自洛谷，原作者为

	Singercoder Our true self lies within.

搬运于2025-08-24 22:22:06，当前版本为作者最后更新于2020-06-07 01:45:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

序言

• km算法的学习过程可谓艰辛，各种奇怪的hack层出不穷，而网络资料给出的debug也不是很全面。特此写下本篇题解供各oier参考。
• 后记的相关内容总结了km算法在应用时的一些小技巧，和一些有趣的hack及其应对方式。（因为本蒟蒻的确被卡了很多次，求大神轻喷。）
• 鸣谢：$ltao$。没有他，我不可能见到这些神奇的hack与debug，也无法得到有效且及时的质疑与纠正。

算法介绍

• 算法简介：km算法（Kuhn－Munkres算法），是一种在二分图上求解最大权完美匹配的算法，用邻接矩阵存图即可。相比费用流较高的复杂度，km算法有着更为优秀的效率，但局限性在于只能做匹配，而不像费用流那样灵活可变。

• 前置知识：匈牙利算法的bfs写法（附上匈牙利和km算法的bfs模板，可供参考，欢迎交流）

• km算法的核心思路在于：

  • 定义顶标$lx[i],ly[i]$，则对于每一条边，都有性质$lx[u]+ly[v]>=e[u][v]$。
  • 当且仅当$lx[u]+ly[v]=e[u][v]$时，我们称该边为相等边。
  • 所有点和所有相等边所组成的子图称为相等子图。
  • 核心算法：贪心地将増广所需的边中，边权最大的那些边变成相等边，即逐渐扩大相等子图。
  • 核心性质：扩大相等子图至其刚好有完美匹配时，该匹配即为原图的最大权完美匹配（很好理解，因为扩大相等子图的过程是贪心的）

  由此，我们便能将km算法简单地理解为：匈牙利算法+扩大相等子图

• 顶标的设计是km的精髓，这里参考ltao的定义：

$lx[i]$左部点的顶标

$ly[i]$右部点的顶标

$vx[i]$左部点遍历标记

$vy[i]$右部点遍历标记

$px[i]$左部点匹配

$px[i]$右部点匹配

$slack[i]$对于指向右部点$i$的所有边，$min(lx[u]+ly[i]-e[u][i])$的值，即松弛量（初始化为inf）

PS:当slack[i]=0，表示对于右部点i，相等子图中有一条指向它的边

而修改顶标的思路可以具体看代码，核心语句如下（copy的是下面bfs正解的过程）：

	if(vx[i])lx[i]-=d;//对于vx[i]=0的情况我们根本没有讨论，实际上也并不需要讨论
	if(vy[i])ly[i]+=d;else slack[i]-=d;

这样修改的目的是保证已在相等子图中的边两侧顶标和不变，同时通过左部点顶标的减小实现向相等子图中拉进新相等边的目的。

如果还不是很理解可以画个图，对于原图中某条边：

1. $vx[u]=0,vy[v]=0$，则$slack[v]$不变（未遍历到的=>不修改）
2. $vx[u]=1,vy[v]=1$，则$slack[v]$不变（已遍历到的=>该边为相等边=>修改后依旧为相等边）
3. $vx[u]=0,vy[v]=1$，则$slack[v]+=d$（未知该边是否为相等边=>若非相等边则依旧非；若为相等边，则会被拉出相等子图，但既然$vy[i]=1$，则本次増广必然不会用到这条边，拉出也无所谓；况且通过u去找非匹配的v也不方便。因此不必而且不便于体现在程序中。而初学者也不必深究，不处理即可）
4. $vx[u]=1,vy[v]=0$，则$slack[v]-=d$（该边非相等边=>修改后可能为相等边=>可能提供新増广路。很重要，这是扩大相等子图的原理）

这里提供ltao's blog以加深理解。他充分讨论了修改顶标对所有边产生的影响，还提出了关于序号3的一些非常重要的观点，本篇题解在后记中也会提到。

模板分析（p6577）

首先提示坑点：

1. 边权最小约-1e7，所以如果要添加虚边将图补成完全图，记得初始边权设为$-inf$。（不补全而直接忽视不存在边在本题也可行，依照个人习惯即可）
2. 权值和需要用long long​存储。

直接打出匈牙利dfs写法+扩大相等子图的模板，初学者一定要先练熟这个。

const int MAXN=510;

int n,m;
int e[MAXN][MAXN];

int lx[MAXN],ly[MAXN],py[MAXN],d;
bool vx[MAXN],vy[MAXN];

bool dfs(int u)
{
	vx[u]=1;
	for(int i=1;i<=n;++i)if(!vy[i])
	{
		if(lx[u]+ly[i]==e[u][i])
		{
			vy[i]=1;
			if(!py[i] || dfs(py[i]))
			{
				py[i]=u;
				vy[i]=1;
				return 1;
			}
		}
		else d=min(d,lx[u]+ly[i]-e[u][i]);
	}
	return 0;
}

int main()
{
	for(int i=1;i<=n;++i)
	{
		while(1)
		{
			memset(vx,0,sizeof(vx));
			memset(vy,0,sizeof(vy));
			d=inf;
			if(dfs(i))break;
			for(int j=1;j<=n;++j)
			{
				if(vx[j])lx[j]-=d;
				if(vy[j])ly[j]+=d;
			}
		}
	}
}

结果成功tle，不得不说卡km+dfs的题目真的不多。

我们简单分析一下复杂度：

• 每次扩大相等子图最少只能加入一条相等边，也就是最多会进行$n^2$次扩大相等子图。
• 每次扩大相等子图后都需要进行dfs増广，单次复杂度可达$n^2$。

也就是说，km+dfs的复杂度完全可以卡到$n^4$。

---

考虑如何优化，我们不难发现每次扩大相等子图之后，都要从増广起点重新开始dfs，这个过程是有明显的时间浪费的。

能不能在扩大相等子图之后，保留上次状态呢？

答案是可行的，我们只需要换用bfs写法：在每次扩大子图后，都记录一下新加入的相等边所为我们提供的新増广方向，然后从此处继续寻找増广路即可。

扩大相等子图复杂度：

• 每次扩大相等子图最少只能加入一条相等边，也就是最多会进行$n^2$次扩大相等子图。
• 每次扩大相等子图复杂度$n$，无需额外増广，从上次起点继续増广即可。

増广复杂度：

• 每个左部点需要1次増广，共有$n$个左部点。
• 单次増广复杂度可达$n^2$。

由此可见，通过简单的状态延续策略，我们成功将km算法的复杂度降到了$n^3$。

const int MAXN=510;

int n,m;
int e[MAXN][MAXN];

int lx[MAXN],ly[MAXN],slack[MAXN];
int px[MAXN],py[MAXN],pre[MAXN];
bool vx[MAXN],vy[MAXN];

queue<int> q;
void aug(int v)
{
	int t;
	while(v)
	{
		t=px[pre[v]];
		px[pre[v]]=v;
		py[v]=pre[v];
		v=t;
	}
}
void bfs(int s)
{
	memset(vx,0,sizeof(vx));
	memset(vy,0,sizeof(vy));
	fill(slack+1,slack+n+1,inf);
	
	while(!q.empty())q.pop();
	q.push(s);
	
	while(1)
	{
		while(!q.empty())
		{
			int u=q.front();q.pop();
			vx[u]=1;
			for(int i=1;i<=n;++i)if(!vy[i])
			{
				if(lx[u]+ly[i]-e[u][i]<slack[i])
				{
					slack[i]=lx[u]+ly[i]-e[u][i];
					pre[i]=u;
					if(slack[i]==0)
					{
						vy[i]=1;
						if(!py[i]){aug(i);return;}
						else q.push(py[i]);
					}
				}
			}
		}
		int d=inf;
		for(int i=1;i<=n;++i)if(!vy[i])d=min(d,slack[i]);
		for(int i=1;i<=n;++i)
		{
			if(vx[i])lx[i]-=d;
			if(vy[i])ly[i]+=d;else slack[i]-=d;
		}
		for(int i=1;i<=n;++i)if(!vy[i])
		{
			if(slack[i]==0)
			{
				vy[i]=1;
				if(!py[i]){aug(i);return;}
				else q.push(py[i]);
			}
		}
	}
}

int main()
{
	for(int i=1;i<=n;++i)bfs(i);
}

还有一种迭代bfs的写法，是榜一$Wendigo$大神所采用的，可能不像队列写法这么易懂，但码量明显大幅下降。

另外$Wendigo$还提到迭代写法可以卡到$n^4$，但在下不是很理解该怎样构造数据，也不清楚队列写法是否同样可以hack，希望评论区有大神可以解答。

这两篇博客分别使用的是队列写法和迭代写法，供参考。

后记

$ltao$在他的题解注释中有一个非常隐蔽的伏笔：

//这个其实是有一点小问题的，但是没啥大问题

说的这么玄学谁能明白啊

1.虚点虚边的添加

因为出题人保证了数据存在完备匹配，所以就算不是完全二分图也可以大胆去跑km。

但有些题目需要特判无解情况，即不存在完美匹配；

还有些题目告诉你，就算非完美匹配也无所谓，为了让权值和最大可以允许某些点无匹配而孤独终生。

这类题目就要求选手对km算法拥有比较清晰的理解，那么请你思考一下，分别应该如何应对？

ok揭晓答案。

首先无论哪种情况，我们都要保证左部点个数小于等于右部点个数，通过为右部点添加虚点来实现。

然后，我们要将原本不存在的边连成虚边。

对于需要特判无解的题目，我们需要极力避免选择虚边，也就是将虚边边权设为$-inf$，如果被迫选了$-inf$的边就输出无解。

对于允许非完美匹配的题目，我们允许选取虚边，也就是将虚边边权设为0即可。

这样，我们就可以在完全二分图上跑km求解。（当然对于无解，你也可以选择只加一个虚点作为退路，跑一般二分图的km，如果该虚点被匹配则必然无解）

不过这只是一种个人比较喜欢的通用策略，对于特判无解的那种题目，还有一种常见策略：

即当$d$很大时，说明某个$slack[i]$很大，无法扩大子图，也就是无解。但为什么这个很大不是$inf$呢？原因在于我们bfs写法为了加速就必须修改顶标同时修改$slack[]$，可能会改变$slack[]=inf$的值，非常不方便判无解。

还有人会说用dfs时如果无解，能保证$d=inf$。但这种写法慢是一方面，另一方面就是我将要提到的死循环hack。

2.可能的死循环hack

dfs写法直接判$d=inf$无解，是有死循环风险的。

这个简单的小hack能坑到很多初学者（包括我），下面详细说一下。

借用ltao的话来说：一共有最多$n^2$条边，却只有$2n$的顶标，这就好像要用$2n$个元来满足$n^2$个方程成立，很明显是存在方程组无解的可能性的！

而体现在原图中便是不是所有边都能成为相等边，而相等子图可能如何设置顶标也无法等于原图！

而体现在算法中，就是总有一些边，我们无论如何也拉不进来，或者拉进一些边的同时拉出一些边。（将相等边拉出相等子图的原理，就是上文提到的$vx[u]=0,vy[v]=1$所导致的结果）

这就会导致这样一种可能的后果：由于dfs的鼠目寸光，我们会先从u遍历到某条非相等边<u,v>，并记录下$d=lx[u]+ly[v]-e[u][v]$；然后在后续的遍历过程中，我们通过其他路径遍历到了v点。 此时，$vx[u]=vy[v]=1$，可$0<d<inf$，我们一方面拉不进这条边，另一方面判不出来无解，只能陷入死循环。（hdu2426的discuss中就有大神造出了这样hack）

那为什么bfs写法就能防止死循环？

因为bfs写法不是在遍历过程中直接记录$d$，而是走遍所有能遍历的点后，用$slack[]$来计算$d$。而且bfs写法判无解通常用虚点虚边，也就能避免死循环情况出现。

---

upd:对hdu2426的hack原理没看太明白的，可以去看看ltao的题解，有我依此做的一个配图样例。（我就不在这里贴出来了）