KM复习_LCA

KM 复习

附：HK 算法求二分图最大匹配

在求二分图最大匹配时，常数更小空间也更小的写法是使用 HK 算法。

其实就是只用了流的有效部分，去除了臃肿的部分。

每次只找最少边数的增广路集合，能多找就多找，至多 $\sqrt n$ 轮（不会证）。

流程：每次把未匹配的左部点扔进队列里 bfs，搜到一个未匹配的右部点时更新全局最短路，当有最短路 $>$ 该最短路时停止更新，然后暴力 dfs 最短路。

只需维护每个左部点连了哪些右部点，可以 bitset 优化。

KM

直到某一天在场上看到了裸的板子（虽然是假题意）然后急急急写不出来才后悔没有复习。

首先线性规划对偶，变成了每个点求一个顶标，满足每条边的两端的顶标和 $\ge$ 边权，求最小的顶标和。

相等子图：里面有所有的点，对于一组合法顶标，称边权 恰好等于 两端顶标和的边在相等子图内。

显然，若相等子图内有完美匹配，则这就是最大权完美匹配，因为其他完美匹配在这张图上也是 $\le$ 顶标和的。

KM 算法告诉我们，一定能求出一组合法顶标使得相等子图内有完美匹配。

我们用匈牙利树的结构来分析 KM 算法的过程。

• 仿照匈牙利算法，仅在相等子图上跑。
• 遍历完能遍历的点后，统计奇数层向外连边（不统计返祖边）的 $u=\min(s_x+s_y-w_{x,y})$。
• 将已遍历的部分点，奇数层顶标 $-u$，偶数层顶标 $+u$，则全图至少解锁了一条奇数层向外的边。
• 若解锁的边指向非匹配点，则我们找到增广路，否则我们可以继续搜。

对这个算法进行正确性分析：

• 首先没有奇数层到奇数层的横叉边，返祖边不受影响，所以我们解锁的一定是奇数层向未搜到的部分。
• 挂在奇数层的边都更倾向于解锁了，挂在偶数层的边由于偶数层权值增加，不会受到威胁。
• 原来的相等子图中的匈牙利树部分不会损失边，只会扩展边。

直接模拟其实十分好写，详见 luogu 第一篇题解，这是四方的。

经典改用 bfs 写法是处理完顶标直接跳到新的部分去搜，码量较大。

存在一种 $\rm slack$ 优化的 bfs 写法，具体地，对于每个右部点我们维护相连的所有左部点的最小顶标边权差 $r_y=\min(s_x+s_y-w_{x,y})$，每次我们都往相等子图内加入一个点。

每次我们加入一个左部点的时候，我们更新右部点的 $\rm slack$，然后取出 $\rm slack$ 最小的右部点，更新已搜过点的顶标，如果该右部点是非匹配点那么找到了增广路，如果是匹配点就去搜它。