【学习笔记】一般图最大匹配(带花树)

学了一发带花树,感觉很高妙。

然后顺便复习了一下二分图匹配and学了一下随机匹配。

🌼🌲:Blossom Tree.

从匹配到二分图匹配

从匹配到增广路

给定一张图 $G=\{\mathrm{V,E}\}$ ,一组两两没有交点的边集 $\rm M\subseteq E$ 称之为 $G$ 的一组匹配。边数最多的匹配称之为 $G$ 的最大匹配。其中 $\forall (u,v)\in \mathrm{M}$ 称之为匹配边,否则称为非匹配边

称一个点在匹配中当且仅当它是某跳匹配边的端点。称匹配中的点为匹配点,不在匹配中的点为未盖点 。与某个匹配点共匹配边的另一个端点称之为该点的配偶

嗯,定义朗诵完了…然后大概就是考虑怎么找匹配。大概就是增广路算法。定义增广路是这样的一种图上的路径:

1、路径的起点和终点均为未盖点。

2、路径上匹配边、未匹配边交替出现。

据此可以知道

1、一条增广路必然只会有奇数条边。

2、增广路上非匹配边比匹配边多 $1$ 。

3、如果将所有边的状态取反,那么匹配数 $+1$ 。

于是有定理

如果一个匹配 $\mathrm{M}$ 是图 $G$ 的最大匹配,当且仅当 $G’=\rm \{V,E\setminus M\}$ 中不存在增广路。

这…必要性还是比较显然的吧。充分性的话,鸽了鸽了。

于是考虑如果要求解一张图里的最大匹配,可以通过不断找增广路的方式来进行。

从增广路到二分图匹配

二分图最重要的一个特征:没有奇环。

考虑这样为什么能简化找匹配的过程呢?发现本质上每次找增广路,就是在找一条长度为奇数的路径。那么考虑这样一个做法:

遍历每个当前的未盖点 $u$ :

1、如果 $\exists (u,v)$ 使得 $v$ 也是未盖点,那么可以直接让 $v$ 匹配上,匹配数 $+1$ 。

2、如果对于某个匹配点 $v$ 的配偶 $p$ ,可以找到除了 $v$ 之外的另一个配偶 $q$ ,那么就让 $p$ 和 $q$ 配对、$u$ 和 $v$ 配对。总匹配数 $+1$ 。

看上去十分合理?这样就可以保证每次找到的都会是一条极长的增广路。考虑倒着归纳来证明这个事实【此时考虑的是重匹配(即状态取反)之前】:

1、如果对于 $u$ 找到了一个未盖点 $v$ ,那么 $(u,v)$ 是增广路。

2、如果对于某个匹配点 $v$ 的配偶 $p$ ,可以找到除了 $v$ 之外的另一个配偶 $q$ ,那么 $p,q$ 之间的路径一定是增广路,边 $(u,v)$ 之间一定也是增广路。同时又因为边 $(v,p)$ 为匹配边,所以路径 $u-v-p-q$ 一定是一条长度为奇数的增广路。

由此可知,这样找的路一定是增广路。同时本质上这个算法就是在对每一条边进行定向,比如 $(u\to v)$ 就代表着找到了一组 $u,v$ 匹配且可能会让 $v$ 调整匹配。那么于是一般的二分图匹配算法就是这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool path(int u){
for (int k = head[u] ; k ; k = E[k].next){
if (!vis[to(k)]){
vis [to(k)] = 1 ;
if (!used[to(k)] || path(used[to(k)])){
used[to(k)] = u ;
return 1 ;
}
}
}
return 0 ;
}
int main(){
cin >> N >> M >> Ew ;
while(Ew --) scanf("%d%d", &A, &B), Add(A, B) ;
for (R int i = 1 ; i <= N ; ++ i)
memset(vis, 0, sizeof(vis)), Ans += (int)path(i) ;
cout << Ans << endl ; return 0 ;
}

值得注意的是,如果存在某个节点寻找匹配失败,那么 dfs 过程中访问到所有结点和边会组成一个树形态,称之为交错树

但是这样在一般无向图上会存在什么问题吗?考虑一个这样的环

一开始从 $x$ 出发找到 $y$ ,$x,y$ 均变为匹配点。之后跳过 $y$ 因为 $y$ 已经被匹配。之后来到 $z$ 。发现对于 $z$ 而言,$z$ 找 $x$ ,$x$ 找配偶 $y$,$y$ 发现自己的临边中 $z$ 还没被匹配,于是就匹配 $z$ 。发现这样最后会使得 $z$ 既匹配了 $x$ 又匹配了 $y$ 。原因是什么?发现原因在于这是一个奇环。奇环是会存在对于一条边的两个临边在黑白染色之后呈同色,这不符合匹配的定义。

于是…匈牙利就挂在了一般图上。

从二分图匹配到带花树

考虑二分图匹配直接移植的问题就在于奇环。那么考虑如何消除奇环的贡献。于是就要引入带花树这个算法(英: Blosssom Algorithm)。

带花树本质是考虑奇环匹配的本质,即如果让奇环自己单独匹配,会发生什么。发现一个长为 $2\cdot k+1$ 的奇环无论何时都可以贡献 $k$ 对匹配,并且余下一个未盖点。于是带花树会考虑,在处理增广路时直接把奇环缩成一个点,称之为 。之后在缩完花的新图上继续找增广路。

然后证明的话…大概就是考虑如果原图存在增广路,那么新图也必然存在,反之亦然。具体证明咕了咕了。

…其实带花树难点就只是在实现上。考虑不去显示地缩点,而是用并查集维护每个点在哪一朵花里面。然后考虑用 bfs 的方式对当前点 $u$ 的交错树染色。考虑将点染为 $\alpha$ 类和 $\beta$ 类,那么本质上需要进行如下流程:

-1、初始结点 $u$ 为 $\alpha$ 类。

0、当前点和当前邻居结点在同一朵花里,直接 continue

1、当前点为 $\alpha$ 类,当前邻居结点为 $\beta$ 类,直接 continue

2、当前点为 $\alpha $ 类,当前邻居结点未被染色:

考虑如果邻居结点是匹配点,那么将邻居结点的配偶加入队列,同时将邻居结点染为 $\alpha$ 类;如果邻居结点是未盖点,那么直接将从 $u$ 开始的这一段增广路取反之后,匹配数 $+1$,并将邻居结点染为 $\beta$ 类之后跳出。

3、当前点为 $\alpha$ 类,当前邻居结点也为 $\alpha$ 类:

考虑这时就找到了一个 $u,v$ 都在的奇环。考虑首先为了缩掉这个奇环,需要找到它们在交错树上的 lca。那么于此就需要记录每个点在交错树上的前驱结点(父节点) $fa_x$。 之后考虑,由于这个奇环上的每一个点都可以当做唯一被剩下的那个未盖点去与环外的点匹配,那么就需要将环上所有的 $\beta$ 类点加入队列。同时由于这个环可以自由匹配,所以环上相邻的点应该是彼此的 $fa$ 。于是这个操作就可以看作是在开花(blossom)

然后实现方面…似乎就这么多细节了。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
int n, m ;

namespace Blossom_Tree{
int ans ;
int num ;
int h, t ;
int q[N] ;
int fa[N] ;
int dfn[N] ;
int pre[N] ;
int clr[N] ;
int match[N] ;
void Init(){
for (int i = 1 ; i <= n ; ++ i)
fa[i] = i, match[i] = clr[i] = pre[i] = 0 ;
}
int find(int x){
if (x == fa[x]) return x ;
return fa[x] = find(fa[x]) ;
}
int lca(int x, int y){
++ num ;
x = find(x) ;
y = find(y) ; int z ;
while (dfn[x] != num){
dfn[x] = num ;
z = find(pre[match[x]]) ;
x = z ; if (y) swap(x, y) ;
}
return x ;
}
void blossom(int x, int y, int z){//z=lca(x, y)
// cout << x << " " << y << " " << z << '\n' ;
while (find(x) != z){
pre[x] = y ;
y = match[x] ;
fa[x] = fa[y] = z ;//2
if (clr[y] > 1)
clr[y] = 1, q[++ t] = y ;
x = pre[match[x]] ;
}
}
int do_match(int x){
h = 1, t = 0 ;
q[++ t] = x ; clr[x] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
fa[i] = i, clr[i] = pre[i] = 0 ;
while (h <= t){
int x = q[h ++] ;
// cout << x << " " << h << " " << t << " " << head[x] << " &\n" ;
for (int k = head[x] ; k ; k = next(k)){
if (clr[to(k)] > 1) continue ;
if (find(x) == find(to(k))) continue ;
if (!clr[to(k)]){
clr[to(k)] = 2 ;
pre[to(k)] = x ;
if (!match[to(k)]){
int z = to(k), y ;
while (z){
y = match[pre[z]] ;//1
match[pre[z]] = z ;
match[z] = pre[z] ; z = y ;
}
return 1 ;
}
clr[match[to(k)]] = 1 ;
q[++ t] = match[to(k)] ;
}
else {
int z = lca(x, to(k)) ;
blossom(x, to(k), z) ;
blossom(to(k), x, z) ;
}
}
// puts("xxxx") ;
}
return 0 ;
}
void work(){
int x, y ;
for (int i = 1 ; i <= m ; ++ i)
x = qr(), y = qr(), add_e(x, y), add_e(y, x) ;
for (int i = 1 ; i <= n ; ++ i)
if (!match[i]) ans += do_match(i) ;
cout << ans << '\n' ; debug(match, 1, n) ;
}
}
using namespace Blossom_Tree ;

考虑因为本质上是在 $u$ 的匹配过程中缩点,抽象出模型来就是在交错树上缩花and开花,于是这个算法被叫做「带花树🌼🌲」。

从带花树到弃疗

总结一下。大概带花树的流程其实也不难写,只是正确性不是那么显然。同时注意到每次 bfs 时,一个点最多入队 $O(n)$ 次,这一点可以通过最多有 $O(n)$ 个不同的点让当前点加入花/加入队列来理解。于是复杂度总复杂度就是 $O(n^3)$ ,但事实上根本跑不满。

一般而言可以拿 $O(nm)$ 当作理论下界。关于这个理论下界有两点:

1、实现下界比理论下界还要低不少。

2、理论上这个下界应该是比较松的,因为会存在某些点进队出队许多次,所以不能单纯地用单次 bfs 复杂度来分析。

总之…还是 $O(\texttt{能过})$ 比较到位吧。

好玄学啊好玄学啊。

从弃疗到相信随机化

本来想着在洛谷随便写一发,$90$ 就 $90$ 咱也不带怂的

然后就…过掉了…

顺便也过掉了 uoj 的 $52$ 组数据和 $43+$ 组的 Extra Task

大概就是考虑随机匹配。随机匹配的思想就是,不找环,只找长度为奇数的增广路。这样做相当于强制断环为链,正确性难以保证。但是考虑如果多做几次,错误率就会大大下降。于是考虑多做几次这样的匹配。注意到这样做很容易被卡掉,只需要多几个奇环顺便构造一下加边顺序就可以了。所以就可以每次走的时候将边表随一下即可。

然后…用 rand() 很容易被卡掉,因为值域很小,而边数比 $32768$ 大得多。所以用 mt19937 就可以了。

值得一提的是,以下代码为了保证正确,卡了时,大概是卡了 $0.85s$ 左右。但是十分有趣的是…洛谷的数据在 $0.0005s=0.5ms$ 的卡时范围之内都能过掉…这…咱也不知道该说什么好。

upd: 随机匹配似乎是无敌了。在 uoj 试了一发卡时 $0.005s=5ms$ 的情况,依旧无压力过掉了所有 $hack$ 数据。

这个故事告诉我们:题是众生一般题,水是天下一样水。随机匹配 txdy!!!!

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
int ans ;
int n, m ;
int vis[N] ;
int match[N] ;

clock_t st ;

mt19937 g_f ;

il db now_time(){
return (double)(clock() - st) / CLOCKS_PER_SEC ;
}
int do_match(int x, mt19937 g_f){
cout << x << ' ' ;
shuffle(E[x].begin(), E[x].end(), g_f) ; vis[x] = 1 ;
for (auto y : E[x])
if (!match[y])
return vis[y] = 1, match[y] = x, match[x] = y, 1 ;
for (auto y : E[x]){
int z = match[y] ;
if (vis[z]) continue ;
match[x] = y, match[y] = x, match[z] = 0 ;
if (do_match(z, g_f)) return 1 ;
match[y] = z, match[z] = y, match[x] = 0 ;
}
return 0 ;
}
int main(){
random_device seed ;
mt19937 g_f(seed()) ;
cin >> n >> m ; int x, y, z ;
for (int i = 1 ; i <= m ; ++ i)
x = qr(), y = qr(), add_e(x, y) ; st = clock() ;
while (now_time() < 0.85){
for (int i = 1 ; i <= n ; ++ i)
if (!match[i])
fill(vis + 1, vis + n + 1, 0), ans += do_match(i, g_f), puts("") ;
}
cout << ans << '\n' ;
return debug(match, 1, n), 0 ;
}

后来发现…uoj卡时卡到 $0.8ms$ 也是能过的。这大概就是看脸了吧。