隐藏
带花树学习笔记 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

带花树学习笔记

发表于 更新于 分类于 Valine：

带花树是来解决一类一般图匹配问题的算法。
带花树的应用并不广泛，目前仅停留在模板题阶段。
其实维基百科讲得很好，其实我就是翻译了一下。

增广路

学了二分图匹配的应该对增广路很熟悉，但我们还是提一下。

如果在一个$M$匹配的图$G$中，有一个点$v$是孤立的指没有与其匹配的点。一条在$G$中的路径如果其边在$M$中交替出现，则称为交错路（alternating path）。一条增广路（augmenting path）$P$是一条开始并结束于不相同的孤立点的交错路。
在增广路中不是匹配的边比是匹配的边多，因此增广路的边条数为奇数。
一个匹配在增广路上的增广即为异或操作：$M_1=M\,xor\,P$。

如果在$G$中没有$M$的增广路了，那么匹配$M$是$G$的最大匹配。如果$M$不是最大匹配，那么它一定可以被增广。

因此我们可以一直执行增广操作直到不能再增广，最后就可以得到图$G$的最大匹配$M$。

花与收缩

在一个$M$匹配的图$G$中，一朵花$B$是一个图$G$中的包含$2k+1$条边的奇环，其中$k$条边在$M$中，并存在从环上任意一个点$v$（花根）到一个孤立点$w$的交错路（花茎）。

如何找到一朵花？

  • 从一个孤立的点$w$开始遍历图。
  • 从孤立点$w$开始遍历，标记$w$为$o$型点（out of M）。
  • 交替地用$i$和$o$标记结点，保证无两个相邻结点有相同标记。
  • 如果找到两个相邻结点均含有标记$o$，那么我们就找到了一个奇环与一朵花。

定义收缩图$G’$是图$G$将所有花$B$缩为点后的图。
定义收缩匹配$M’$是在$G’$中对应的匹配$M$。

$G’$含有$M’$的增广路当且仅当$G$含有$M$的增广路，且任何$M’$在图$G’$的增广路$P’$都可以通过展开收缩的花还原$G$中的匹配$M$。
因此如果存在任意一条增广路$P’$通过收缩的花$V_B$，都可以找到合适的增广路通过花$B$。

更多细节

  • 如果$P’$在图$G’$中经过$u\rightarrow V_B\rightarrow w$，这条增广路可以在$G$中被替换为$u\rightarrow (u’\rightarrow\ldots\rightarrow w’)\rightarrow w$，其中$u’$与$w’$在花$B$中。路径$u’\rightarrow w’$的选择需保证构成的新增广路仍然是交替的。（其中$u’$既在花$B$中也在匹配$M$中（花根），$w’\rightarrow w$是一条增广路）

  • 若$P’$在$V_B$结束，这条增广路可以在$G$中被替换为$u\rightarrow(u’\rightarrow\ldots\rightarrow v’)$，其中$u’$与$v’$在花$B$中。路径$u’\rightarrow v’$的选择需保证狗构成的新增广路仍然是交替的。（其中$v’$是孤立的（花根），$u\rightarrow u’$是一条增广路）

因此花可以被收缩成点，这是带花树算法的核心。

思考

接下来的就不搬运维基百科的了。

思考1

为什么我们仅仅将 花根与环外匹配的 环称为花？为什么不能 花根与环内匹配 不能称为一朵花？

因为带花树缩花的原因是为了防止寻找增广路的时候绕环一圈后重新进入花茎而发生干扰。

如果花茎是这样的：

此时$o$标记的点相邻，因为队列中的点均为$o$标记点（下一部分会讲到），所以可能会与花茎发生干扰。

如果花茎是这样的：

$i$标记点相邻，显然不会与花茎发生干扰。
虽然该环是一个奇环，但显然当前的交错路不会是花茎，当前的花茎相连的点也不是花根。
上图若要形成一朵花，应该是下图这样的形式：

思考2

为什么我们不对偶环进行处理？

因为如果是偶环，那么从任意一个点开始进行标记，标记是不会发生冲突的（偶环是二分图）。故不会对花茎产生干扰，限制其匹配即可。

思考3

如何输出匹配方案？

我们不进行显式缩点，记录每一个点所属于的花，每一次寻找到增广路后就可以直接沿着增广路维护信息。

思考4（achen提出）

不进行显示缩点，如果有多朵花嵌套会对算法过程有影响吗？

答案是不会！
我们只需要考虑多个花嵌套时对单条增广路的影响。

如图，我们发现，无论花如何嵌套，我们始终可以找出沿着花边走的一条合法交错路。（在上一部分已经说明过可以找出一朵花的合法路径，因此也可以推广到嵌套）

寻找增广路

对于每个结点我们记录以下信息：

  • $type$：这个点的类型，$0$为$o$型点，$1$为$i$型点。
  • $match$：这个点所匹配的点。注意$match$是双向指针，如果$match[u]=v$，则$match[v]=u$。
  • $pre$：这个点在交错路中相邻但不和当前点构成匹配的点，若$match[u]$与其他点匹配了，则需要将$match[u]$置为$pre[u]$。注意$pre$在非花的增广路中是单向的，由在交错路中的后继指向其前驱，在花中$pre$指针是双向的。
  • $father$：这个点所属的花，若不属于任何花则置为本身。为了方便输出方案，我们不进行显式缩点，因此需要引入这个指针。

我们依次从每一个孤立点开始宽搜，并依次用$i$与$o$标记图上的点。

  • 若寻找到一个未被标记的未匹配点：将其标记为$i$型点，找到一条增广路，更新并维护该增广路的信息，完成增广。
  • 若寻找到一个未被标记的点，但其已经被匹配，将其标记为$i$型点，并将其匹配的点标记为$o$型点，加入队列。
  • 若寻找到一个已经被标记的$i$型点，说明此时构成偶环，直接无视。
  • 若寻找到一个已经被标记的$o$型点，说明此时构成奇环且构成花，在当前扩展出的交错路上找到其公共祖先$lca$，$lca$此时为花根，沿着两侧的花边爬到花根，将路径上的结点$father$指针更新，标记全部更新为$o$，并将$pre$指针变为双向指针。

思考5

为什么链的交错路上的$pre$是单向指针，而花上的$pre$指针是双向指针？

因为在链的交错路上增广方向确定，只需要单向指针即可，而花上我们不确定会从什么方向增广，故需要双向指针。

模板（UOJ79 一般图最大匹配）

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=505;

int n,m,father[maxn],vst[maxn],match[maxn],pre[maxn],Type[maxn];
vector<int>edges[maxn];
queue<int>Q;

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

int LCA(int x,int y) {
	static int times=0;
	times++;
	x=father[x],y=father[y]; //已知环位置
	while(vst[x]!=times) {
		if(x) {
			vst[x]=times;
			x=father[pre[match[x]]];
		}
		swap(x,y);
	}
	return x;
}

void blossom(int x,int y,int lca) {
	while(father[x]!=lca) {
		pre[x]=y;
		y=match[x];
		if(Type[y]==1) {
			Type[y]=0;
			Q.push(y);
		}
		father[x]=father[y]=father[lca];
		x=pre[y];
	}
}

int Augument(int s) {
	for(int i=1; i<=n; i++)father[i]=i;
	memset(Type,-1,sizeof(Type));
	Q=queue<int>();
	Type[s]=0;
	Q.push(s); //仅入队o型点
	while(!Q.empty()) {
		int Now=Q.front();
		Q.pop();
		for(int Next:edges[Now]) {
			if(Type[Next]==-1) {
				pre[Next]=Now;
				Type[Next]=1; //标记为i型点
				if(!match[Next]) {
					for(int to=Next,from=Now; to; from=pre[to]) {
						match[to]=from;
						swap(match[from],to);
					}
					return true;
				}
				Type[match[Next]]=0;
				Q.push(match[Next]);
			} else if(Type[Next]==0&&father[Now]!=father[Next]) {
				int lca=LCA(Now,Next);
				blossom(Now,Next,lca);
				blossom(Next,Now,lca);
			}
		}
	}
	return false;
}

int ans=0;

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge(x,y);
		AddEdge(y,x);
	}
	for(int i=n; i>=1; i--)
		if(!match[i])ans+=Augument(i);
	printf("%d\n",ans);
	for(int i=1; i<=n; i++)printf("%d ",match[i]);
	return 0;
}

时间复杂度

我们枚举孤立点并将所有点入队，若找到花需要遍历整朵花，因此时间复杂度为$O(n^3)$。

带花树解决带权匹配问题

我不会，也不会写23333。
估计也没几个人会写233333。

参考资料

相关文章
姥爷们赏瓶冰阔落吧~