二分图最大匹配
为了描述方便将两个集合分成左和右两个部分,所有匹配边都是横跨左右两个集合,可以假想成男女配对。
假设图有 n 个顶点,m 条边。
增广路算法 Augmenting Path Algorithm
因为增广路长度为奇数,路径起始点非左即右,所以我们先考虑从左边的未匹配点找增广路。
注意到因为交错路的关系,增广路上的第奇数条边都是非匹配边,第偶数条边都是匹配边,于是左到右都是非匹配边,右到左都是匹配边。
于是我们给二分图 定向,问题转换成,有向图中从给定起点找一条简单路径走到某个未匹配点,此问题等价给定起始点 s 能否走到终点 t。
那么只要从起始点开始 DFS 遍历直到找到某个未匹配点,O(m)。
未找到增广路时,我们拓展的路也称为 交错树。
因为要枚举 n 个点,总复杂度为 O(nm)。
代码
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 | struct augment_path {
vector<vector<int> > g;
vector<int> pa; // 匹配
vector<int> pb;
vector<int> vis; // 访问
int n, m; // 两个点集中的顶点数量
int dfn; // 时间戳记
int res; // 匹配数
augment_path(int _n, int _m) : n(_n), m(_m) {
assert(0 <= n && 0 <= m);
pa = vector<int>(n, -1);
pb = vector<int>(m, -1);
vis = vector<int>(n);
g.resize(n);
res = 0;
dfn = 0;
}
void add(int from, int to) {
assert(0 <= from && from < n && 0 <= to && to < m);
g[from].push_back(to);
}
bool dfs(int v) {
vis[v] = dfn;
for (int u : g[v]) {
if (pb[u] == -1) {
pb[u] = v;
pa[v] = u;
return true;
}
}
for (int u : g[v]) {
if (vis[pb[u]] != dfn && dfs(pb[u])) {
pa[v] = u;
pb[u] = v;
return true;
}
}
return false;
}
int solve() {
while (true) {
dfn++;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (pa[i] == -1 && dfs(i)) {
cnt++;
}
}
if (cnt == 0) {
break;
}
res += cnt;
}
return res;
}
};
|
转为网络最大流模型
二分图最大匹配可以转换成网络流模型。
将源点连上左边所有点,右边所有点连上汇点,容量皆为 1。原来的每条边从左往右连边,容量也皆为 1,最大流即最大匹配。
如果使用 Dinic 算法 求该网络的最大流,可在 O(\sqrt{n}m) 求出。
Dinic 算法分成两部分,第一部分用 O(m) 时间 BFS 建立网络流,第二步是 O(nm) 时间 DFS 进行增广。
但因为容量为 1,所以实际时间复杂度为 O(m)。
接下来前 O(\sqrt{n}) 轮,复杂度为 O(\sqrt{n}m)。O(\sqrt{n}) 轮以后,每条增广路径长度至少 \sqrt{n},而这样的路径不超过 \sqrt{n},所以此时最多只需要跑 \sqrt{n} 轮,整体复杂度为 O(\sqrt{n}m)。
代码可以参考 Dinic 算法 的参考实现,这里不再给出。
补充
二分图最大独立集
选最多的点,满足两两之间没有边相连。
二分图中,最大独立集 =n- 最大匹配。
二分图最小点覆盖
选最少的点,满足每条边至少有一个端点被选,不难发现补集是独立集。
二分图中,最小点覆盖 =n- 最大独立集。
习题
UOJ #78. 二分图最大匹配
模板题
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 | #include <bits/stdc++.h>
using namespace std;
struct augment_path {
vector<vector<int> > g;
vector<int> pa; // 匹配
vector<int> pb;
vector<int> vis; // 访问
int n, m; // 顶点和边的数量
int dfn; // 时间戳记
int res; // 匹配数
augment_path(int _n, int _m) : n(_n), m(_m) {
assert(0 <= n && 0 <= m);
pa = vector<int>(n, -1);
pb = vector<int>(m, -1);
vis = vector<int>(n);
g.resize(n);
res = 0;
dfn = 0;
}
void add(int from, int to) {
assert(0 <= from && from < n && 0 <= to && to < m);
g[from].push_back(to);
}
bool dfs(int v) {
vis[v] = dfn;
for (int u : g[v]) {
if (pb[u] == -1) {
pb[u] = v;
pa[v] = u;
return true;
}
}
for (int u : g[v]) {
if (vis[pb[u]] != dfn && dfs(pb[u])) {
pa[v] = u;
pb[u] = v;
return true;
}
}
return false;
}
int solve() {
while (true) {
dfn++;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (pa[i] == -1 && dfs(i)) {
cnt++;
}
}
if (cnt == 0) {
break;
}
res += cnt;
}
return res;
}
};
int main() {
int n, m, e;
cin >> n >> m >> e;
augment_path solver(n, m);
int u, v;
for (int i = 0; i < e; i++) {
cin >> u >> v;
u--, v--;
solver.add(u, v);
}
cout << solver.solve() << "\n";
for (int i = 0; i < n; i++) {
cout << solver.pa[i] + 1 << " ";
}
cout << "\n";
}
|
P1640 [SCOI2010]连续攻击游戏
None
Codeforces 1139E - Maximize Mex
None
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:accelsao, thallium, Chrogeek, Enter-tainer, ksyx, StudyingFather, H-J-Granger, Henry-ZHR, countercurrent-time, william-song-shy
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用