图的匹配算法

参考文献:IOI国家集训队2015年论文——《浅谈图的匹配算法及其应用》。

增广路

设 $P$ 为图中一条简单路径,如果满足:

  1. $P$ 的起点和重点都是未盖点
  2. $P$ 中的边中匹配边和非匹配边交错出现。

则称 $P$ 是一条增广路

特别地,我们把满足条件 $2$ 的简单路径称为交替路

增广:增广路上非匹配边数量比匹配边数量多 $1$,如果把这条路径取反,则当前匹配大小会增加 $1$。这个过程称为增广。

定理:一个匹配 $M$ 是图 $G$ 的最大匹配,充要条件是 $G$ 中不存在增广路。

二分图最大匹配

Dinic

你肯定会的

时间复杂度 $O(E \sqrt{V})$

增广路算法(匈牙利)

因为增广路的长度为奇数,所以路径的起点和终点一定分居在二分图左右两侧,不妨从左边的每个未盖点找增广路。

注意到增广路上第奇数次走的是非匹配边,第偶数次走的是匹配边。这说明从左到右走的都是非匹配边,从右到左走的都是匹配边。

枚举左边每一个未盖点 $u$ ,从 $u$ 开始 $DFS$,每个点记录一个访问标记,以保证至多访问一次,当找到右侧某个未盖点时结束遍历。

找一次增广路的复杂度为 $O(E)$,枚举未盖点的复杂度是 $O(V)$,因此总复杂度为 $O(VE)$。

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
// O(VE)
struct MaxMatch {
int n, clk;
vector<int> G[maxn];
int vis[maxn], ls[maxn], rs[maxn];
void init(int n) {
this->n = n;
for (int i = 0; i < n; i++) G[i].clear();
memset(rs, -1, sizeof(rs));
memset(ls, -1, sizeof(ls));
memset(vis, -1, sizeof(vis));
}
void addEdge(int u, int v) { G[u].push_back(v); }
bool dfs(int u) {
for (auto &v : G[u]) {
if (vis[v] == clk) continue;
vis[v] = clk;
if (rs[v] == -1 || dfs(rs[v])) {
ls[u] = v;
rs[v] = u;
return true;
}
}
return false;
}
int match() {
int ret = 0;
for (clk = 0; clk < n; clk++)
if (dfs(clk)) ++ret;
return ret;
}
};

二分图最大匹配关键点

关键点:一定在最大匹配中的点。

先求任意一个最大匹配 $M$,要找的关键点此时一定都是匹配点。考虑 $M$ 中的一个匹配点 $p$,设 $M’$ 为某个不包含 $p$ 的最大匹配。设对称差 $D = M \bigoplus M’$ ,则 $D$ 中一定存在一条以 $p$ 为端点的偶交替链,且这条链的另一端不在 $M$ 中。

所以我们给二分图定向:匹配边从右到左,非匹配边从左到右。从左侧每个未盖点出发 $DFS$,给所到达的左侧点打上标记。最终左侧每个没有标记的匹配点即为关键点。

因为每个点最多访问一次,因此复杂度为 $O(V + E)$

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
struct MaxMatch {
int n, m, clk;
vector<int> G[maxn], rG[maxn];
int vis[maxn], ls[maxn], rs[maxn];
void init(int n, int m) {
this->n = n, this->m = m;
for (int i = 0; i < n; i++) G[i].clear();
for (int i = 0; i < m; i++) rG[i].clear();
memset(rs, -1, sizeof(rs));
memset(ls, -1, sizeof(ls));
memset(vis, -1, sizeof(vis));
}
void addEdge(int u, int v) {
G[u].push_back(v);
rG[v].push_back(u);
}
bool dfs(int u) {
for (auto &v : G[u]) {
if (vis[v] == clk) continue;
vis[v] = clk;
if (rs[v] == -1 || dfs(rs[v])) {
ls[u] = v;
rs[v] = u;
return true;
}
}
return false;
}
int match() {
int ret = 0;
for (clk = 0; clk < n; clk++)
if (dfs(clk)) ++ret;
return ret;
}
// ---------------------------------------
bool lskp[maxn], rskp[maxn];
void dfs_kp_ls(int u) {
vis[u] = 1;
for (auto &v : G[u]) {
if (rs[v] == -1 || vis[rs[v]]) continue;
dfs_kp_ls(rs[v]);
}
}
void dfs_kp_rs(int u) {
vis[u] = 1;
for (auto &v : rG[u]) {
if (ls[v] == -1 || vis[ls[v]]) continue;
dfs_kp_rs(ls[v]);
}
}
int findKeyPoint() {
// match();
memset(lskp, 0, sizeof(lskp));
memset(rskp, 0, sizeof(rskp));

memset(vis, 0, sizeof(vis));
int ret = 0;
for (int i = 0; i < n; i++)
if (ls[i] == -1) dfs_kp_ls(i);
for (int i = 0; i < n; i++)
if (!vis[i]) lskp[i] = 1, ret++;

memset(vis, 0, sizeof(vis));
for (int i = 0; i < m; i++)
if (rs[i] == -1) dfs_kp_rs(i);
for (int i = 0; i < m; i++)
if (!vis[i]) rskp[i] = 1, ret++;

return ret;
}
};

二分图最大匹配关键边

关键边:一定在最大匹配中的边

先求任意一个最大匹配 $M$,要找的关键边此时一定都是匹配边。考虑 $M$ 中的一个匹配边 $e$,设 $M’$ 为某个不包含 $e$ 的最大匹配。设对称差 $D = M \bigoplus M’$ ,则 $e$ 在 $D$ 中一定属于一个偶交替链偶交替环

对于 $e$ 属于一个偶交替链的情况:
那么这条链的某一端一定是未盖点。说明 $e$ 的某个端点能通过交替路走到未盖点,即某个端点是非关键点。因此只需判断 $e$ 的两个端点是否存在非关键点。若存在,则 $e$ 为非关键边。

对于 $e$ 属于一个偶交替环的情况:
我们给二分图定向:匹配边从左到右,非匹配边从右到左,再检测 $e$ 是否存在于某个环中(二分图不存在奇环)。这用 $Tarjan$ 求强连通分量即可。

所以时间复杂度为 $O(V + E)$

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
struct Tarjan {
vector<int> G[maxn];
int scc, dfs_clock, top; // scc: 强连通分量的数量
bool instack[maxn];
int dfn[maxn], low[maxn], belong[maxn], Stack[maxn];
void tarjan(int u) {
dfn[u] = low[u] = ++dfs_clock;
instack[u] = true;
Stack[top++] = u;
for (auto &v : G[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++scc;
int cnt = 0;
int now;
while (top > 0) {
now = Stack[--top];
instack[now] = false;
belong[now] = u;
++cnt;
if (now == u) break;
}
}
}
void solve(int n) {
memset(instack, 0, sizeof(instack));
memset(dfn, 0, sizeof(dfn));
scc = dfs_clock = top = 0;
for (int i = 0; i < n; i++) {
if (!dfn[i]) tarjan(i);
}
}
} tarjan;

// n+m
struct MaxMatch {
int n, m, clk;
vector<int> G[maxn], rG[maxn];
int vis[maxn], ls[maxn], rs[maxn];
void init(int n, int m) {
this->n = n, this->m = m;
for (int i = 0; i < n; i++) G[i].clear();
for (int i = 0; i < m; i++) rG[i].clear();
memset(rs, -1, sizeof(rs));
memset(ls, -1, sizeof(ls));
memset(vis, -1, sizeof(vis));
edges.clear();
}
void addEdge(int u, int v) {
G[u].push_back(v);
rG[v].push_back(u);
edges.push_back({u, v});
}
bool dfs(int u) {
for (auto &v : G[u]) {
if (vis[v] == clk) continue;
vis[v] = clk;
if (rs[v] == -1 || dfs(rs[v])) {
ls[u] = v;
rs[v] = u;
return true;
}
}
return false;
}
int match() {
int ret = 0;
for (clk = 0; clk < n; clk++)
if (dfs(clk)) ++ret;
return ret;
}
// ---------------------------------------
bool lskp[maxn], rskp[maxn];
void dfs_kp_ls(int u) {
vis[u] = 1;
for (auto &v : G[u]) {
if (rs[v] == -1 || vis[rs[v]]) continue;
dfs_kp_ls(rs[v]);
}
}
void dfs_kp_rs(int u) {
vis[u] = 1;
for (auto &v : rG[u]) {
if (ls[v] == -1 || vis[ls[v]]) continue;
dfs_kp_rs(ls[v]);
}
}
// O(n+m)
int findKeyPoint() {
// match();
memset(lskp, 0, sizeof(lskp));
memset(rskp, 0, sizeof(rskp));

memset(vis, 0, sizeof(vis));
int ret = 0;
for (int i = 0; i < n; i++)
if (ls[i] == -1) dfs_kp_ls(i);
for (int i = 0; i < n; i++)
if (!vis[i]) lskp[i] = 1, ret++;

memset(vis, 0, sizeof(vis));
for (int i = 0; i < m; i++)
if (rs[i] == -1) dfs_kp_rs(i);
for (int i = 0; i < m; i++)
if (!vis[i]) rskp[i] = 1, ret++;

return ret;
}
// -----------------------------------------
vector<pair<int, int>> edges;
bool ke[maxn];
int findKeyEdge() {
findKeyPoint();
memset(ke, 0, sizeof(ke));
for (int i = 0; i < n + m; i++) tarjan.G[i].clear();
for (auto &e : edges) {
if (ls[e.first] == e.second) {
tarjan.G[e.first].push_back(e.second + n);
} else {
tarjan.G[e.second + n].push_back(e.first);
}
}
tarjan.solve(n + m);
int ret = 0;
for (int i = 0; i < edges.size(); i++) {
auto e = edges[i];
if (ls[e.first] != e.second) continue;
if (!lskp[e.first] || !rskp[e.second]) continue;
if (tarjan.belong[e.first] != tarjan.belong[e.second + n]) {
ke[i] = 1;
ret++;
continue;
}
}
return ret;
}
};

二分图最大独立集

独立集

给定图 $G=(V,E)$,$V’$ 是 $V$ 的一个非空子集。若 $V’$ 的任何两个顶点 $u,v$ 都不是同一条边的两个端点,则称 $V’$ 是 $G$ 的一个空子图。设 $V’$ 是 $G$ 的空子图,若 $V’$ 任意增加一个 $G$ 中不在 $V’$ 中的点后都不是空子图,则称 $V’$ 是 $G$ 的独立集。$G$ 中所含顶点数最多的独立集 $V’$ 称为 $G$ 的最大独立集。

做法

设最大独立集为 $V’$。

首先求一个图的最大匹配 $M$,那么所有的未盖点必定都在 $V’$ 中(不然匹配数就会增加)。

然后考虑从每个匹配边中选一个点放到 $V’$ 中,这样 $V’$ 中的点数就是 $|V| - |M|$。

做法很显然:就是从每一个未盖点出发,依次决定路上点是否可以放到 $V’$ 中。

但是这么做可能会遇到矛盾,就是一条边的两个点中一个是未盖点一个是匹配点,但经过上述做法后,这两个点可能都被放入 $V’$ 中。实际上这是不可能的,因为我们发现如果有这种情况存在,那么必定存在一条奇数长度增广路,使得当前匹配并不是最大匹配,这与 $M$ 是最大匹配矛盾。

因此 $|V’| = |V| - |M|$。

若要输出方案,则从每个未盖点出发,依次决定路上每个点是否可以放入 $V’$ 即可。复杂度 $O(|V| + |E|)$

二分图最小点覆盖

最小点覆盖是说:选最少的点,满足每条边都至少有一个端点被选。

任意点覆盖的补集都是独立集,任意独立集的补集都是点覆盖。

最小点覆盖 = $V$ - 最大独立集 = 最大匹配 $M$

一般图最大匹配

带花树算法

一般图和二分图的唯一区别在于可能存在奇环,这就导致如果我们对奇环进行增广,就会出现某个点同时在两条匹配边上的情况。

观察发现,可以通过把奇环缩点,所得到的新图 $G’$。
则 $G$ 中存在增广路 $\Leftrightarrow$ $G’$ 中存在增广路。

所以还是运用增广路算法,在找到奇环时只要进行缩点即可。

时间复杂度 $O(V^3)$

代码

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
struct MaxMatch {
vector<int> G[maxn];
queue<int> Q;
int n, clk;
int match[maxn], par[maxn];
int Type[maxn], pre[maxn], vis[maxn];

void init(int n) {
this->n = n;
clk = 0;
for (int i = 1; i <= n; i++) G[i].clear(), vis[i] = 0, match[i] = 0;
}
void addEdge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}

int LCA(int x, int y) {
clk++;
x = par[x], y = par[y];
while (vis[x] != clk) {
if (x) {
vis[x] = clk;
x = par[pre[match[x]]];
}
swap(x, y);
}
return x;
}
void blossom(int x, int y, int lca) {
while (par[x] != lca) {
pre[x] = y;
y = match[x];
if (Type[y] == 1) {
Type[y] = 0;
Q.push(y);
}
par[x] = par[y] = par[lca];
x = pre[y];
}
}
int Augument(int s) {
for (int i = 1; i <= n; i++) par[i] = i, Type[i] = -1;
Q = queue<int>();
Type[s] = 0;
Q.push(s);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (auto &v : G[u]) {
if (Type[v] == -1) {
pre[v] = u;
Type[v] = 1;
if (!match[v]) {
for (int to = v, from = u; to; from = pre[to]) {
match[to] = from;
swap(match[from], to);
}
return true;
}
Type[match[v]] = 0;
Q.push(match[v]);
} else if (Type[v] == 0 && par[u] != par[v]) {
int lca = LCA(u, v);
blossom(u, v, lca);
blossom(v, u, lca);
}
}
}
return false;
}

int work() {
int ans = 0;
for (int i = 1; i <= n; i++) // 注意匹配顺序
if (!match[i]) ans += Augument(i);
return ans;
}
} match;

匹配顺序

带花树在匹配数不增加时不会丢弃之前已经匹配的边。因此对于某些题目在匹配时要注意匹配顺序。

建图技巧

一般图匹配最大的特点在于存在奇环。且奇环中未匹配的边数一定比匹配的边数大 $1$。

例题

奇环性质
挑战NPC

棋盘模型(交替路的理解)
zoj3316
hdu3446

生成指定度数的子图
hdu3551

二分图最大权匹配

一般图最大权匹配