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

ix35 · 2020-05-28 21:15:33 · 题解

之前写的有锅，现在修正并整理，重发一下。

二分图最大权匹配

对于给定二分图 G=(V,E)，每条边有一个权值 w_i，我们想要找出一组匹配，使得其中包含的所有边权值和最大，称为二分图最大权匹配。

注意，如果给定的 E 不包含所有可能的边，那么最大权匹配不一定是最大匹配。

为了求解这个问题，让我们再次借助线性规划工具：

\max \sum\limits_{i=1}^m w_ix_i

\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

\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）。
下一个访问的左部点将是刚才取出的右部点的匹配点，这就是一个寻找增广路的过程，而当那个右部点是非匹配点时，我们已经找到了一条增广路。
重复上述过程，依次加入所有左部点，最后就求出了最小顶标和问题的解，也就是最大权完美匹配的方案。

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;
}