题解 P6577 【【模板】二分图最大权完美匹配】

之前写的有锅，现在修正并整理，重发一下。 ## 二分图最大权匹配 对于给定二分图 $G=(V,E)$，每条边有一个权值 $w_i$，我们想要找出一组匹配，使得其中包含的所有边权值和最大，称为**二分图最大权匹配。** 注意，如果给定的 $E$ 不包含所有可能的边，那么最大权匹配**不一定**是最大匹配。 为了求解这个问题，让我们再次借助线性规划工具： $$\max \sum\limits_{i=1}^m w_ix_i$$ $$s.t. \begin{cases} \sum\limits_{i=1}^mw(j,i)x_i\leq 1 \\ x_i\ge 0 \end{cases}$$ 其中 $w(j,i)$ 表示边 $i$ 是否以点 $j$ 为端点，其实这个问题就是在最大匹配的基础上加上了每条边的权值 $w_i$。 仍旧将它对偶，得到： $$\min\sum\limits_{j=1}^n y_j $$ $$s.t. \begin{cases} \sum\limits_{j=1}^n w(j,i)y_j\ge w_i \\ y_j\ge 0 \end{cases}$$ 我们将对偶问题中的变量 $y_j$ 称为顶点 $j$ 的**顶标**，那么问题转化成了： **最小顶标和问题：给定二分图，给每个点一个顶标，使得每条边两端点的顶标和不小于边权，且所有点顶标和最小。** 不过，再次我们需要做一些补充： - 在上面的线性规划证明中，我们要求 $w_i\ge 0$，即边权非负。 - 但是，如果存在 $w_i<0$，那么应该不能直接套用上面的方法证明（顶标有可能是负数，不满足线性规划的条件），我们稍后叙述算法时也将证明：存在 $w_i<0$ 时，下面的算法也能够通过最小顶标和问题解出一种最大权的完美匹配。 接下来我们将介绍 KM 算法，KM 算法通过解决最小顶标和问题，可以求出给定二分图的一组权值和最大的**完美匹配**。 在叙述算法过程前，先说说怎么将原先的问题（最大权匹配）转化成最大权完美匹配： - 如果要求 $w_i\ge 0$ 的最大权匹配，那么我们只需要将所有不存在的边视为边权为 $0$ 的边，如果左右两部点数不相等则补为相等，就转化成了最大权完美匹配问题； - 如果要求存在 $w_i<0$ 的最大权完美匹配（当然也可以是权值都非负的），就将不存在的边权值设为 $-\infty$； - 如果要求存在 $w_i<0$ 的最大权匹配，那么当然是把所有负权边删掉，变成非负情况。 我们将左部点 $i$ 的顶标称为 $A_i$，右部点 $j$ 的顶标称为 $B_j$，我们要求 $A_i+B_j\ge d(i,j)$，其中 $d(i,j)$ 为 $i,j$ 之间的边权（按照上面的方法补全为完全二分图）。 **相等子图**定义为所有满足 $A_i+B_j=d(i,j)$ 的边构成的子图。 **命题：相等子图中若存在完美匹配，则这组完美匹配是原图的一个最大权完美匹配。** 证明：考虑这组完美匹配的边权和，根据相等子图定义应当是 $\sum A_i+\sum B_j$，而对于原图中任意的一组完美匹配，由于 $d(i,j)\leq A_i+B_j$，所以边权和不超过 $\sum A_i+\sum B_j$，所以这组完美匹配是最大的。 接下来考虑：如果相等子图中没有完美匹配，尝试通过调整顶标使得相等子图中的最大匹配变大，从而最终形成完美匹配。 假设此时左侧有点 $x$ 在相等子图的最大匹配中为非匹配点，从 $x$ 开始尝试在相等子图中寻找增广路（由于是最大匹配了所以必然无法找到），然后我们将访问到的左部点顶标减小 $\Delta$，右部点顶标增大 $\Delta$，考虑这样做的影响： - 对于匹配边，两边必然都访问到或都不访问到，因此 $A_i+B_j$ 不变，仍然属于相等子图； - 对于某个以访问到的左部点为一端的非匹配边，由于 $A_i$ 减小，有可能被新加入相等子图中。 所以这么做不会影响原先匹配，但可以增加新的边进入相等子图，从而继续增广，而我们只要取 $\Delta$ 为所有以左部的被访问到的点为一端的边 $(i,j)$ 中最小的 $A_i+B_j-d(i,j)$ 即可，这样至少加进了一条边（但 $\Delta$ 不能大于这个值，否则不符合顶标的要求）。 于是我们首先任意设定初始合法顶标（如右部点都为 $0$，左部点都为相连边权最大值），每次加入一个左部点，按照上面要求尝试在相等子图中增广，如果成功则直接增大匹配，否则按照上述过程进行顶标调整，直接实现这一算法就得到了基于 DFS 的 KM 算法，复杂度较高。 考虑优化这一算法，我们下面介绍一种 **slack 优化的基于 BFS 的 KM 算法**。 - 在每次加入一个左部点，尝试增广时，模拟匈牙利算法求增广路的过程，而对于右部每个点 $y$，记录 $slack_y$ 表示这一轮已经访问的左侧点 $x$ 中，$A_x+B_y-d(x,y)$ 的最小值。 - 当我们访问到一个左部点时，先用它更新所有右部点的 $slack$ 值，接下来我们取出右部 $slack$ 最小的一个点，将其值设为 $\Delta$，然后将当前已经访问的左部点顶标减小 $\Delta$，当前已访问的右部点顶标增加 $\Delta$，并更新 $slack$ 数组（实际上就是每个点的 $slack$ 也需要减小 $\Delta$）。 - 下一个访问的左部点将是刚才取出的右部点的匹配点，这就是一个寻找增广路的过程，而当那个右部点是非匹配点时，我们已经找到了一条增广路。 - 重复上述过程，依次加入所有左部点，最后就求出了最小顶标和问题的解，也就是最大权完美匹配的方案。 --- ```cpp void bfs (int x) { memset(vis,0,sizeof(vis)); memset(s,0x3f,sizeof(s)); memset(pre,0,sizeof(pre)); cur=pn=0,mat[0]=x; while (1) { x=mat[cur]; ll dis=INF; vis[cur]=1; for (int i=n+1;i<=n+n;i++) { if (vis[i]) {continue;} ll tmp=w[i]+w[x]-d[x][i-n]; if (tmp<s[i]) {s[i]=tmp,pre[i]=cur;} if (s[i]<dis) {dis=s[i],pn=i;} } w[mat[0]]-=dis,w[0]+=dis; for (int i=n+1;i<=n+n;i++) { if (vis[i]) {w[i]+=dis,w[mat[i]]-=dis;} else {s[i]-=dis;} } cur=pn; if (!mat[cur]) {break;} } while (cur) { mat[cur]=mat[pre[cur]]; cur=pre[cur]; } return; } ```