[KM算法]uoj#80 二分图最大权匹配

待我称王封你为后i 2021-12-22 16:41 200阅读 0赞

题意：给定二分图，有边权，求最大边权匹配。边权非负。

解：KM算法求解最大权完备匹配。

完备匹配就是点数少的那一边每个点都有匹配。

为了让完备匹配与最大权匹配等价，我们添加若干条0边使之成为完全二分图(自造名词别在意......)

为了让左边成为点数较少的一边，我们还要添加一些虚点，m = max(n,m)

然后求解完备匹配。

KM的DFS写法会被卡成n4，如果你不在意可以写......反正在uoj上会被卡爆。

模板就不放了，反正没啥用，放了还我 误 我 自 己。

过程就是一次为每个点寻找匹配。首先每个点都有个顶标(期望匹配值)，最后要使得每一条匹配边(x, y)满足w\[x\] + w\[y\] = val(x, y)

然后每个右边的点还有个need数组，一般是叫做slack，就是松弛量，也就是当前这个点最少要把w减去多少才能匹配上。

还有个D是min slack，也就是全局最少减少D才能得到匹配。

匹配的时候跟匈牙利一样DFS，注意到一个点之后如果w\[x\] + w\[y\] = val(x, y)则这条边可用，打上vis，否则用差值更新need y

如果没有匹配就update一遍，每个有vis的左边减去D，右边加上D。然后继续直到有匹配为止。

BFS写法

这个我不太懂...话说DFS本来就不懂了，还纠结这个干啥。

右边节点有个pre数组表示它是谁更新来的，也就是如果它进入增广路，那么它前面的右边节点是pre

在BFS函数里首先设置BFS起点是右边0匹配左边x，然后尝试为x找到增广路。

枚举每个未被vis的y，得到w\[x\] + w\[y\]与val(x, y)的差值。

用这个差值更新need\[y\]，如果差值比need\[y\]小，就表明y的前一个节点是mat\[x\]的话会更佳，令pre\[y\] = u(u表示正在匹配x的节点，也就是上一个x准备匹配的节点)

用need\[y\]更新D，如果need\[y\] < D则表明全局上下一个点选择y更优，令nex = y(此处nex是下一轮的u)

然后更新一遍，让所有vis的右边节点(当然也包括一开始我们虚拟跟x匹配的右边0号点)w += D，而与之匹配的左边节点w -= D

结束条件是找到的这个u没有匹配。此时增广路就找到了。

然后把交错路取反，也就是每个u的匹配变成上一个u的匹配，直到倒数第二个u匹配x。

啊我到底在口胡些什么

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //thanks to yyb
     2 #include <cstdio>
     3 #include <algorithm>
     4 #include <cstring>
     5 
     6 typedef long long LL;
     7 const int N = 410;
     8 const LL INF = 0x3f3f3f3f3f3f3f3f;
     9 
    10 int vis[N * 2], mat[N * 2], Time, pre[N * 2], n, m;
    11 LL val[N][N], w[N * 2], need[N * 2];
    12 
    13 void BFS(int x) {
    14     memset(need, 0x3f, sizeof(need));
    15     memset(pre, 0, sizeof(pre));
    16     int u = 0, nex;
    17     mat[u] = x;
    18     do {
    19         x = mat[u];
    20         LL D = INF;
    21         vis[u] = Time;
    22         for(int y = n + 1; y <= n + m; y++) {
    23             if(vis[y] == Time) {
    24                 continue;
    25             }
    26             LL t = w[x] + w[y] - val[x][y - n];
    27             if(t < need[y]) { // update need pre
    28                 need[y] = t;
    29                 pre[y] = u;
    30             }
    31             if(need[y] < D) { // update D nex
    32                 D = need[y];
    33                 nex = y;
    34             }
    35         }
    36         // update
    37         w[mat[0]] -= D; // do not forget! 
    38         w[0] += D;
    39         for(int i = n + 1; i <= n + m; i++) {
    40             if(vis[i] == Time) {
    41                 w[mat[i]] -= D;
    42                 w[i] += D;
    43             }
    44             else {
    45                 need[i] -= D;
    46             }
    47         }
    48         u = nex;
    49     } while(mat[u]);
    50 
    51     while(u) { // update path 
    52         mat[u] = mat[pre[u]];
    53         u = pre[u];
    54     }
    55 
    56     return;
    57 }
    58 
    59 int main() {
    60     int q;
    61     scanf("%d%d%d", &n, &m, &q);
    62     m = std::max(n, m);
    63     for(int i = 1; i <= q; i++) {
    64         int x, y;
    65         LL z;
    66         scanf("%d%d%lld", &x, &y, &z);
    67         val[x][y] = std::max(val[x][y], z);
    68         w[x] = std::max(w[x], val[x][y]);
    69     }
    70     for(int i = 1; i <= n; i++) {
    71         ++Time; // ++Time
    72         BFS(i);
    73     }
    74     LL ans = 0;
    75     for(int i = n + 1; i <= n + m; i++) {
    76         if(val[mat[i]][i - n]) { // do not forget " - n"!
    77             mat[mat[i]] = i;
    78             ans += val[mat[i]][i - n];
    79         }
    80     }
    81     printf("%lld\n", ans);
    82     for(int i = 1; i <= n; i++) {
    83         printf("%d ", mat[i] ? mat[i] - n : mat[i]);
    84     }
    85     return 0;
    86 }

AC代码

最后感谢YYB神犇，我是照抄他的代码的%%%%%%。

转载于:https://www.cnblogs.com/huyufeifei/p/10350763.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/5fc3f72f89004fbe989efee68fa9178d.png