_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

带花树

Problem

UOJ79.

某机房里有nn个OIer,其中有nn个男生,00个女生。现在他们要两两配对。

mm个关系,每个关系是一个无序对(ai,bi)(a_i,b_i),表示这两个人之间愿意配对。

求:最多能配成多少对,并找出一组方案。

说人话:一般图最大匹配。

Algorithm

既然是匹配,我们能不能直接模仿匈牙利算法呢?答案是不可以(废话,可以的话还要什么带花树啊)。

原因是:我们在二分图中,如果dfs找增广路时经过某个点找不到,那么我们可以证明这一轮中这个点的确是无用的(也即,这一轮里所有的增广路都不经过这个点),于是我们就能保证每个点至多走一遍,时间复杂度得到带花树 但是如果是一般图,这个性质不一般成立。比如下图:

flower-tree.jpg

图中红线是已匹配的边。那么,如果我从11开始dfs时先经过22,那么接下来就只能到44(因为只能走匹配边),然后是5,35,3,同时我们会给这四个节点都打一个“找不到增广路”的标记。

但是实际上存在1354261\rightarrow3\rightarrow5\rightarrow4\rightarrow2\rightarrow6这条增广路。仔细观察我们就能发现:这种现象之所以存在,是由于奇环1354211-3-5-4-2-1的存在(如果没有奇环,就变成了二分图匹配,这时候匈牙利算法就是对的)。

那么,对于奇环,有什么后果呢?显然,如果我们dfs出了一个奇环,那么无论环上那个点dfs出了增广路都是可行的。(例如,上图中,如果从55处dfs出一条增广路,使得55匹配到别的点且33成为未盖点,那么可以走131-3。同样,如果55被孤立,我们可以走12451-2-4-5来把55匹配上)

于是,我们可以把一个奇环当做一个点(这个奇环被称为“花”,这就是带花树名字的来历),然后继续找增广路。

形式化的,如果我们在图G=(V,E)G=(V,E)中找到了一个奇环v1v2vkv1v_1-v_2-\dots-v_k-v_1(称为“花”),其中v1v_1是环上的深度最小的结点,不难证明,v1v_1的配偶不在此花中(因为在找到这个花之前所有边组成一个二分图,那么由于v1v_1向下dfs/bfs出了一个花,它一定是X结点,只有X结点会向外扩展),且(v2,v3),(v4,v5)(vk1,vk)(v_2,v_3),(v_4,v_5)\dots(v_{k-1},v_{k})都是匹配边。那么我们构建一个图

G=(V,E),V=V/{v2,v3,vk},E={(f(a),f(b))(a,b)E,a,bvi,i=1k}\begin{aligned}G'&=(V', E'),\\ V'&=V/\{v_2,v_3\dots,v_k\},\\ E'&=\{(f(a),f(b))|(a,b)\in E, a,b\neq v_i, i=1\dots k\}\end{aligned}

其中f(vi)=v1,f(a)=a(avj),i,j=1,2,,kf(v_i)=v_1, f(a)=a(a\neq v_j), i, j=1,2,\dots,k

并且原本GG中的所有匹配除掉(v2,v3),(v4,v5)(vk1,vk)(v_2,v_3),(v_4,v_5)\dots(v_{k-1},v_{k})构成GG'的一个匹配。

那么,GG中存在增广路\LeftrightarrowGG'中存在增广路。

证明:

\Rightarrow:对于GG中的任意一条增广路,若其不经过这朵花,那么在GG'中也存在这条增广路;否则,令这条从ss开始的增广路上的最后一个在花上的点为vjv_j,那么这条增广路形如 svjts\leadsto v_j \leadsto t,我们在GG'上构造如下增广路:先从sv1ts \leadsto v_1 \leadsto t,其中第一段路程沿着bfs/dfs树走,第二段路程沿着原图中的增广路走,唯一不同的是vjv_j变成了v1v_1(这是合法的,因为所有从vjv_j出发的边都被连到了v1v_1上,而且我们根据所有vv都是已盖点可以知道vjv_j出发的边是非匹配边)。 \Leftarrow:对于GG'中的一条增广路,若它不经过v1v_1,则GG中也存在;否则,设这条增广路为sv1xts\leadsto v_1\rightarrow x \leadsto txx可能等于tt),根据EE'的定义存在(vi,x)E(v_i, x)\in E,从而我们构造GG中的增广路:sv1vixts\leadsto v_1\leadsto v_i \rightarrow x \leadsto t,其中第一段和第三段不变(因为增广路上v1v_1至多出现1次,所以这两段在GG中存在),第二段是在花里走(或者精确一点,若ii是奇数,走v1v2viv_1\rightarrow v_2 \dots v_i,否则走v1vkviv_1\rightarrow v_k \dots v_i。证毕。

bfs时,我们可以O(n)O(n)求出LCA并O(kn)O(kn)缩花,从而单次bfs至多O(n2)O(n^2),总复杂度至多O(n3)O(n^3)

实现上,我们不实际缩点,而是对于每个点维护一个fafa,表示它所处的最大的花的LCA(就是v1v_1)。由于花里可能还有花,这个fafa要用并查集维护。在证明中构造增广路是通过判断ii奇偶性,但实际上我们可以直接维护每个点要往哪边走,也即维护一个linkilink_i表示如果ii失配要和谁匹配(例如,linkv2=v1,linkv3=v4link_{v_2}=v_1,link_{v_3}=v_4)。找LCA的时候直接暴力O(n)O(n),但要注意只找每个并查集的根节点(因为非根节点都缩到花里了);缩花时要注意如果两个点已经在一朵花里就不要再缩了。

Code

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
#include <algorithm>
#include <cstdio>
const int N = 700;
const int M = N * N * 2;
int pre[N], nxt[M], to[M], n, cnt;
int mate[N], link[N], vis[N], fa[N];
int que[N], hd, tl;
void addEdge(int x, int y) {
nxt[cnt] = pre[x];
to[pre[x] = cnt++] = y;
}
int Find(int x) { return fa[x] == x ? x : fa[x] = Find(fa[x]); }
int LCA(int x, int y) {
static int ss[N], tim;
++tim;
while (ss[x] != tim) {
if (x) { ss[x] = tim; x = Find(link[mate[x]]); }
std::swap(x, y);
}
return x;
}
void Flower(int x, int y, int p) {
while (Find(x) != p) {
link[x] = y;
fa[y = mate[x]] = fa[x] = p;
if (vis[y] == 1) vis[que[tl++] = y] = 2;
x = link[y];
}
}
bool match(int x) {
hd = tl = 0;
for (int i = 1; i <= n; ++i) vis[fa[i] = i] = 0;
vis[que[tl++] = x] = 2;
while (hd < tl) {
x = que[hd++];
for (int i = pre[x]; ~i; i = nxt[i]) {
int u = to[i];
if (!vis[u]) {
vis[u] = 1;
link[u] = x;
if (!mate[u]) {
while (x) {
x = mate[link[u]];
mate[mate[u] = link[u]] = u;
u = x;
}
return true;
} else
vis[que[tl++] = mate[u]] = 2;
} else if (vis[u] == 2 && Find(u) != Find(x)) {
int p = LCA(x, u);
Flower(x, u, p);
Flower(u, x, p);
}
}
}
return false;
}
int main() {
int m, x, y, ans = 0;
scanf("%d%d", &n ,&m);
std::fill(pre + 1, pre + n + 1, -1);
while (m--) {
scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
if (!mate[x] && !mate[y])
mate[mate[x] = y] = x, ++ans;
}
for (int i = 1; i <= n; ++i)
if (!mate[i] && match(i))
++ans;
printf("%d\n", ans);
for (int i = 1; i <= n; ++i)
printf("%d ", mate[i]);
return 0;
}