KM 算法

学习笔记
3.7k 词

KM 算法用来求二分图最大权完美匹配。当二分图两侧点数不同时，需要将较少部分的点补足，然后将不存在的边视为边权为 −∞-\infty。
下设总点数为 2n2n，其中左部点编号为 1∼n1 \sim n，右部点编号为 n+1∼2nn + 1 \sim 2n。下面认为图是完全二分图，不存在的边边权为 −∞-\infty。

我们给每个点一个点权 lil _ i，称之为顶标。称一组顶标是可行顶标当且仅当对于所有边 (u,v)(u, v) 都满足 wu,v≤lu+lvw _ {u, v} \le l _ u + l _ v。

我们定义相等子图是原图的一个子图 G′=(V,E′)G' = (V, E')，使得 ∀(u,v)∈E′,wu,v=lu+lv\forall (u, v) \in E', w _ {u, v} = l _ u + l _ v。

定理：若一张图的相等子图存在完美匹配，则该匹配即为原图的最大权完美匹配。

证明：

考虑原二分图任意一组完美匹配 MM 的边权和：

val(M)=∑(u,v)∈Mwu,v≤∑(u,v)∈Mlu+lv=∑i=12nlival(M) = \sum\limits _ {(u, v) \in M} w _ {u, v} \le \sum\limits _ {(u, v) \in M} l _ u + l _ v = \sum\limits _ {i = 1} ^ {2n} l _ i

而相等子图的完美匹配 M′M' 的边权和为：

val(M)=∑(u,v)∈Mwu,v=∑(u,v)∈Mlu+lv=∑i=12nlival(M) = \sum\limits _ {(u, v) \in M} w _ {u, v} = \sum\limits _ {(u, v) \in M} l _ u + l _ v = \sum\limits _ {i = 1} ^ {2n} l _ i

原图任意完美匹配的权值都不超过相等子图的完美匹配的权值而相等子图的完美匹配也是原图的完美匹配，得证。

根据定理 1，我们考虑通过不断调整顶标使得相等子图存在完美匹配。

首先初始时我们可以考虑使 li=max⁡(i,u)∈Ewi,u,∀1≤i≤nl _ i = \max _ {(i, u) \in E} w _ {i, u}, \forall 1 \le i \le n，li=0,∀n+1≤i≤2nl _ i = 0, \forall n + 1 \le i \le 2n，显然这是一组可行顶标。

我们维护相等子图的最大匹配，每次我们找到一个未匹配的左部点，然后去找增广路。由于已经是最大匹配，所以必然找不到增广路，但是这样能搜出一棵交错树。
设左部点在交错树中的部分为 SS，剩余的为 S′S'，右部点在交错树中的部分为 TT，剩余的为 T′T'。
我们考虑给 SS 中所有点顶标 −Δ-\Delta，TT 中所有点顶标 +Δ+\Delta：

  • SS 和 TT 间的边依然在相等子图中。
  • S′S' 和 T′T' 间的边没有变化。
  • SS 和 T′T' 间的边可能可以加入相等子图中。
  • S′S' 和 TT 间的边不可能加入相等子图中。

于是我们考虑取 Δ=min⁡u∈S,v∈T′lu+lv−wu,v\Delta = \min _ {u \in S, v \in T'} l _ u + l _ v - w _ {u, v}，这样一定能使至少一条边加入相等子图。

考虑一条边加入相等子图后产生的影响：要么找到增广路，要么交错树增长。因此修改顶标 O(n)O(n) 次一定能找到一条增广路。

直接写可能有点爆炸，有一种 slack 优化的基于 bfs 的 KM 算法。

我们对于每个 v∈T′v \in T'，维护 slackv=min⁡u∈Slu+lv−wu,vslack _ v = \min _ {u \in S} l _ u + l _ v - w _ {u, v}，这样就有 Δ=min⁡v∈T′slackv\Delta = \min _ {v \in T'} slack _ v。搜索时，我们只搜索左部点，然后更新每个点的 slackslack。然后将所有 slackslack 最小的点及与其匹配的左部点都会加入交错树。
具体实现时可以每次只取出一个点，显然这样也是对的。
因为我们要更新一整条增广路，所以对于每个右部点还要维护 matvmat _ v 表示与之匹配的左部点，以及 prevpre _ v 表示与其交错树上父亲匹配的右部点。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 願ったんなら叶えてしまえやって
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, vis[1005], mat[1005], pre[1005];
long long g[505][1005];
long long w[1005], slack[1005];

int main() {
	scanf("%d%d", &n, &m);
	memset(g, ~0x3f, sizeof(g));
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u][n + v] = w;
	}
	for (int i = 1; i <= n; i++) { // 设置初始顶标
		w[i] = ~0x3f3f3f3f3f3f3f3f;
		for (int j = n + 1; j <= n + n; j++) w[i] = max(w[i], (long long)g[i][j]);
	}
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis)); // vis 表示是否在 T 中
		memset(slack, 0x3f, sizeof(slack));
		memset(pre, 0, sizeof(pre));
		int now = i, ri = 0; // now 为当前搜索的左部点，ri 为与之匹配的右部点
		while (1) {
			int id = 0;
			long long delta = 0x3f3f3f3f3f3f3f3f;
			for (int j = n + 1; j <= n + n; j++)
				if (!vis[j]) {
					long long val = w[now] + w[j] - g[now][j];
					if (val < slack[j]) slack[j] = val, pre[j] = ri; // now 是新加入交错树的点，所以首先要用其更新每个点的 slack 和 pre
					if (slack[j] < delta) delta = slack[j], id = j;
				}
			w[i] -= delta;
			for (int j = n + 1; j <= n + n; j++)
				if (vis[j]) w[j] += delta, w[mat[j]] -= delta;
				else slack[j] -= delta;
			vis[ri = id] = 1;
			if (mat[ri]) now = mat[ri];
			else break;
		}
		while (ri) {
			mat[ri] = mat[pre[ri]];
			if (!pre[ri]) {mat[ri] = i; break;}
			ri = pre[ri];
		}
	}
	long long ans = 0;
	for (int i = 1; i <= n + n; i++) ans += w[i];
	printf("%lld\n", ans);
	for (int i = n + 1; i <= n + n; i++) printf("%d ", mat[i]);
	puts("");
	return 0;
}
留言