Mcginn's Blog

Kuhn-Munkres Algorithm

2020/05/10
  1. 背景:带边权的二分图最大权值完美匹配

  2. 顶标概念:顶点权值

  3. 可行顶标:所有 ,都满足

    注:此时还没有开始匹配,是对原图所有边的限制。

  4. 相等子图:包含所有顶点;仅包含 的边。

    问题即转化为求相等子图的完美匹配,此时边权和达到上限

  5. 初始化: 使得初始方案为可行顶标。

  6. 交替路:与匈牙利算法类似,在相等子图中搜索增广路时,如果找不到时我们称此时得到一条交替路。

    如果将交替路 集合的顶标都 集合的顶标都 ,有以下结论:

    • 如果 在相等子图中, 无变化,即该边仍在相等子图中。

    • 如果 不在相等子图中, 在交替路而 不在交替路时 将减少 ,意味着该边有可能加入相等子图中。注意 不能过大,否则会破坏可行顶标这个前提,因此

    注:相等子图中顶标之和 越来越小,以此来加入更多的边使得边权和更大。

  7. 代码模板

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
// find a perfect matching with maximum total cost
// in bipartite graph G=(X,Y;E).
// if you want the total cost minimum, just negative
// cost.
template<typename T>
struct KuhnMunkres {
int n, m, vis[N], pre[N], mth[N];
T INF, Lx[N], Ly[N], slack[N], w[N][N];

void init(int _n, int _m, T _INF) {
n = _n, m = _m, INF = _INF;
// modify weight of non-edge if need
rep(i, 0, n) rep(j, 0, m) w[i][j] = -INF;
}

inline void addEdge(int u, int v, int wgh) {
w[u][v] = wgh;
}

void find(int v) {
rep(i, 0, m + 1) vis[i] = 0, slack[i] = INF;
int u = m;
for (mth[u] = v; mth[u] != -1; u = v) {
vis[u] = 1;
T d = INF;
rep(i, 0, m) if (!vis[i]) {
T att = Lx[mth[u]] + Ly[i] - w[mth[u]][i];
// maintain feasible solution
if (att < slack[i]) slack[i] = att, pre[i] = u;
// find minimum d
if (slack[i] < d) d = slack[v = i];
}
rep(i, 0, m + 1)
if (vis[i]) Lx[mth[i]] -= d, Ly[i] += d;
else slack[i] -= d;
}
// find a augmented path
for(; u != m; u = pre[u]) mth[u] = mth[pre[u]];
}

T solve() {
bool iswap = false;
if (n > m) {
rep(i, 0, n) rep(j, 0, min(i, m))
swap(w[i][j], w[j][i]);
iswap = true, swap(n, m);
}
fill(Lx, Lx + n, 0);
fill(Ly, Ly + m, 0);
fill(mth, mth + m, -1);
rep(i, 0, n) find(i);

T ret = 0;
rep(i, 0, n) ret += Lx[i];
rep(i, 0, m) ret += Ly[i];
if (iswap)
per(i, 0, max(n, m)) swap(Lx[i], Ly[i]);
return ret;
}
};
CATALOG