真·O(n^3) 的非递归的 KM

由来

  2019 年南京 Regional 充分暴露了这个问题，市面上大多数标着 $O(n^3)$ 的 KM 板子实际上是 $O(n^4)$ 的，以致选手如果是用了经典书籍上的板子，或者是网上随便扒的板子，就会 TLE。
  然后最近做题做到了 KM，就想补一个自己的真·$O(n^3)$ 的 KM。网上的 $O(n^3)$ 也都没有教程只能自己啃代码，就想把思路写一下。
  大二了才会 KM 你丢不丢人

  一个简单粗暴的判断板子是 $O(n^4)$ 还是 $O(n^3)$ 的办法：非递归是 $O(n^3)$，递归（用了匈牙利一样的东西）是 $O(n^4)$。
  更加正确的判断方法：拿去交正确的模板题，比如 uoj#80、2019 南京 Regional J（计蒜客复现）。

前置

  要解决的是二分图最大权匹配问题。这是一个线性规划问题，它的对偶问题是最小顶标和问题，KM 的思路就是计算最小顶标和。

$O(n^4)$

  看这位大佬生动的解释就懂了：https://www.cnblogs.com/wenruo/p/5264235.html
  匈牙利是 $O(n^2)$ 的，修改顶标也是 $O(n^2)$ 的，每个点最多 $n$ 次修改顶标，共 $n$ 个点，因此是 $O(n^4)$。

$O(n^3)$

  现在是对于左边的点 $i$，我们来优化它的匹配过程。按照 $O(n^4)$ 的思想，我们是每次匈牙利找增广路，失败了就修改顶标。
  如果我们默认每一次增广都会失败，那么实际上每一次增广的目的就成了最小化 $d$（最小的顶标增量使得相等子图能新加入一条边）。我们把这个 $d$ 挂在右边的结点上，记为 $slack_j$，表示增广路最后到达的右边结点为 $j$ 时，能达到的最小的 $d$。
  那么这就如同 Dijkstra，我们从 $i$ 出发，把右边的结点的 $slack$ 全部松弛一遍，然后找到 $slack$ 最小的 $j$，$slack_j$ 就是本次的顶标增量。（若 $slack_j=0$ 则顶标不动，相当于匈牙利继续，若 $slack_j>0$ 相当于匈牙利失败了要修改顶标。）
  然后尝试匹配 $i$ 和 $j$。若 $j$ 单身，则牵手成功；若 $j$ 名花有主，则尝试绿掉原配增广原配，即从原配出发，把右边的结点的 $slack$ 又松弛一遍……
  直到最后找到了单身的 $j$，就增广成功了。
  于是每个 $j$ 只会被尝试匹配一次，每个原配只会被绿一次增广一次，这样就相当于 $i$ 只做了一次如同 BFS 般的多路增广，所以总时间复杂度为 $O(n^3)$。

  回头看我们默认每一次都增广失败，实际上如果增广成功的话就意味着一路 $slack_j=0$，这种情况被包括了。

  我觉得把它称为多路增广，或者 BFS，都不如 Dijkstra 贴切。

代码

  UPD：区分了左边点数 $nl$ 和右边点数 $nr$

LL lx[maxn],ly[maxn],slack[maxn];
int f[maxn],pre[maxn];							// f[y]表示右边的 y 匹配了左边的谁
bool vis[maxn];
LL KM()
{
	fo(i,1,nl)
	{
		lx[i]=-inf;
		fo(j,1,nr) lx[i]=max(lx[i],mp[i][j]);	// 初始化顶标
	}
	fo(i,1,nl)
	{
		memset(slack,127,sizeof(LL)*(nr+1));
		memset(vis,0,sizeof(bool)*(nr+1));
		f[0]=i;									// 给 i 一个假的原配，统一格式
		int py=0, nextpy;
		for(; f[py]; py=nextpy)					// 当前的左结点为 px，原配 py
		{
			int px=f[py];
			LL d=inf;
			vis[py]=1;
			fo(j,1,nr) if (!vis[j])				// 松弛 slack，及找最小的 slack
			{
				if (lx[px]+ly[j]-mp[px][j]<slack[j]) slack[j]=lx[px]+ly[j]-mp[px][j], pre[j]=py;
				if (slack[j]<d) d=slack[j], nextpy=j;
			}
			fo(j,0,nr) if (vis[j]) lx[f[j]]-=d, ly[j]+=d;	// 修改顶标
				else slack[j]-=d;							// 用于松弛它的顶标已经改了，所以它也要改
		}
		for(; py; py=pre[py]) f[py]=f[pre[py]];		// 修改增广路
	}
	LL re=0;
	fo(i,1,nl) re+=lx[i];
	fo(i,1,nr) re+=ly[i];
	return re;
}

int main()
{
	// nl表示左边的结点数，nr表示右边的结点数，要保证 nl<=nr，即左边有完美匹配
	// (i,j)边权为 mp[i][j]
	printf("%lld\n",KM());
}