二分图最大匹配
为了描述方便将两个集合分成左和右两个部分,所有匹配边都是横跨左右两个集合,可以假想成男女配对。
假设图有
个顶点,
条边。
题目描述
给定一个二分图
,即分左右两部分,各部分之间的点没有边连接,要求选出一些边,使得这些边没有公共顶点,且边的数量最大。
增广路算法 Augmenting Path Algorithm
因为增广路长度为奇数,路径起始点非左即右,所以我们先考虑从左边的未匹配点找增广路。
注意到因为交错路的关系,增广路上的第奇数条边都是非匹配边,第偶数条边都是匹配边,于是左到右都是非匹配边,右到左都是匹配边。
于是我们给二分图 定向,问题转换成,有向图中从给定起点找一条简单路径走到某个未匹配点,此问题等价给定起始点
能否走到终点
。
那么只要从起始点开始 DFS 遍历直到找到某个未匹配点,
。
未找到增广路时,我们拓展的路也称为 交错树。
性质
因为要枚举
个点,总复杂度为
。
实现
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;
}
};
|
转为网络最大流模型
二分图最大匹配可以转换成网络流模型。
将源点连上左边所有点,右边所有点连上汇点,容量皆为
。原来的每条边从左往右连边,容量也皆为
,最大流即最大匹配。
如果使用 Dinic 算法 求该网络的最大流,可在
求出。
Dinic 算法分成两部分,第一部分用
时间 BFS 建立网络流,第二步是
时间 DFS 进行增广。
但因为容量为
,所以实际时间复杂度为
。
接下来前
轮,复杂度为
。
轮以后,每条增广路径长度至少
,而这样的路径不超过
,所以此时最多只需要跑
轮,整体复杂度为
。
代码可以参考 Dinic 算法 的参考实现,这里不再给出。
补充
二分图最小点覆盖(König 定理)
最小点覆盖:选最少的点,满足每条边至少有一个端点被选。
二分图中,最小点覆盖
最大匹配。
证明
将二分图点集分成左右两个集合,使得所有边的两个端点都不在一个集合。
考虑如下构造:从左侧未匹配的节点出发,按照匈牙利算法中增广路的方式走,即先走一条未匹配边,再走一条匹配边。由于已经求出了最大匹配,所以这样的「增广路」一定以匹配边结束,即增广路是不完整的。在所有经过这样「增广路」的节点上打标记。则最后构造的集合是:所有左侧未打标记的节点和所有右侧打了标记的节点。
首先,这个集合的大小等于最大匹配。左边未打标记的点都一定对应着一个匹配边(否则会以这个点为起点开始标记),右边打了标记的节点一定在一条不完整的增广路上,也会对应一个匹配边。假设存在一条匹配边左侧标记了,右侧没标记,左边的点只能是通过另一条匹配边走过来,此时左边的点有两条匹配边,不符合最大匹配的规定;假设存在一条匹配边左侧没标记,右侧标记了,那就会从右边的点沿着这条匹配边走过来,从而左侧也有标记。因此,每一条匹配的边两侧一定都有标记(在不完整的增广路上)或都没有标记,匹配边的两个节点中必然有一个被选中。
其次,这个集合是一个点覆盖。由于我们的构造方式是:所有左侧未打标记的节点和所有右侧打了标记的节点。假设存在左侧打标记且右侧没打标记的边,对于匹配边,上一段已经说明其不存在,对于非匹配边,右端点一定会由这条非匹配边经过,从而被打上标记。因此,这样的构造能够覆盖所有边。
同时,不存在更小的点覆盖。为了覆盖最大匹配的所有边,至少要有最大匹配边数的点数。
二分图最大独立集
最大独立集:选最多的点,满足两两之间没有边相连。
因为在最小点覆盖中,任意一条边都被至少选了一个顶点,所以对于其点集的补集,任意一条边都被至多选了一个顶点,所以不存在边连接两个点集中的点,且该点集最大。因此二分图中,最大独立集
最小点覆盖。
例题
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
81
82 | #include <cassert>
#include <iostream>
#include <vector>
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";
}
|
通过特殊方法把原问题转化成二分图匹配
luogu P1129 矩阵游戏
有一个 01 方阵,每一次可以交换两行或两列,问是否可以交换使得主对角线(左上到右下)全都是 1。
解法
注意到,当存在
个
,使得这些
不在同一行、同一列,那么必然有解,否则必然无解。问题转化成了能否找到这
个
。
考虑对于一个
而言,最终的方案中选了这个
代表这个
的行、列被占用。于是可以建出一个
个左部点、
个右部点的二分图,其中对于某个为
的元素,我们建一条连接它的行的左部点和它的列的右部点。于是就可以二分图匹配了。
代码
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 | #include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int ct, n, t[100010], x, r[100010], ans, vis[100010], dis[100010];
vector<int> to[100010];
queue<int> q;
int DFS(int x) {
if (vis[x]) {
return 0;
}
vis[x] = 1;
for (auto i : to[x]) {
if (!r[i]) {
r[i] = x;
t[x] = i;
return 1;
}
if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
r[i] = x;
t[x] = i;
return 1;
}
}
return 0;
}
int BFS() {
fill(vis + 1, vis + n + 1, 0);
fill(dis + 1, dis + n + 1, 0);
for (int i = 1; i <= n; i++) {
if (!t[i]) {
q.push(i);
dis[i] = 1;
}
}
int f = 0;
for (; q.size(); q.pop()) {
int tmp = q.front();
for (auto i : to[tmp]) {
if (!r[i]) {
f = 1;
}
if (r[i]) {
if (!dis[r[i]]) {
dis[r[i]] = dis[tmp] + 1;
q.push(r[i]);
}
}
}
}
return f;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
for (cin >> ct; ct--;) {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> x;
if (x) {
to[i].push_back(j);
}
}
}
for (; BFS();) {
for (int i = 1; i <= n; i++) {
if (!t[i] && DFS(i)) {
ans++;
}
}
}
cout << (ans == n ? "Yes" : "No") << '\n';
for (int i = 1; i <= n; i++) {
t[i] = r[i] = 0;
to[i].clear();
}
ans = 0;
}
return 0;
}
|
Gym 104427B Lawyers
有
个律师,都被指控有欺诈罪。于是,他们需要互相辩护,确保每一名律师都被释放。
这
个律师有
对信任关系,一个信任关系
表示
可以为
辩护。
任何一个受到辩护的律师都会被无罪释放,除了一个例外:如果
和
互相辩护,他们都会被判有罪。
求是否可以使得每一名律师都被释放。
解法
对于每一个 无序对
,当
可以辩护
,连这个无序对向
的边,反之亦然。
只保存有边相连的
,问题被转化成了一个
个左部点、
个右部点的二分图最大匹配。
代码
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 | #include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
int n, k, u, v, t[200020], r[200020], ans, vis[200020], dis[200020], c;
map<pair<int, int>, int> mp;
vector<int> to[200020];
queue<int> q;
int DFS(int x) {
if (vis[x]) {
return 0;
}
vis[x] = 1;
for (auto i : to[x]) {
if (!r[i]) {
r[i] = x;
t[x] = i;
return 1;
}
if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
r[i] = x;
t[x] = i;
return 1;
}
}
return 0;
}
int BFS() {
fill(vis + 1, vis + n + 1, 0);
fill(dis + 1, dis + n + 1, 0);
for (int i = 1; i <= n; i++) {
if (!t[i]) {
q.push(i);
dis[i] = 1;
}
}
int f = 0;
for (; q.size(); q.pop()) {
int tmp = q.front();
for (auto i : to[tmp]) {
if (!r[i]) {
f = 1;
}
if (r[i]) {
if (!dis[r[i]]) {
dis[r[i]] = dis[tmp] + 1;
q.push(r[i]);
}
}
}
}
return f;
}
void mxf() {
for (; BFS();) {
for (int i = 1; i <= n; i++) {
if (!t[i] && DFS(i)) {
ans++;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= k; i++) {
cin >> u >> v;
if (mp.find({u, v}) == mp.end()) {
mp[{u, v}] = mp[{v, u}] = ++c;
}
to[v].push_back({mp[{u, v}]});
}
mxf();
cout << (ans == n ? "YES" : "NO") << '\n';
ans = 0;
return 0;
}
|
LibreOJ 6002 最小路径覆盖
有一个有向图,现在用顶点不重复的路径覆盖所有顶点,求最少路径数。
解法
对于每一个点,我们建立一个入点、一个出点。对于原图的边
,在
的入点和
的出点连边。
显然一个出点只能和至多一个入点匹配。
于是就变成了一个最大匹配问题。
代码
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 | #include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m, vis[220], dis[220], t[220], r[220], ans, u, v;
vector<int> to[220];
queue<int> q;
int DFS(int x) {
if (vis[x]) {
return 0;
}
vis[x] = 1;
for (auto i : to[x]) {
if (!r[i]) {
r[i] = x;
t[x] = i;
return 1;
}
if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
r[i] = x;
t[x] = i;
return 1;
}
}
return 0;
}
int BFS() {
fill(vis + 1, vis + n + 1, 0);
fill(dis + 1, dis + n + 1, 0);
for (int i = 1; i <= n; i++) {
if (!t[i]) {
q.push(i);
dis[i] = 1;
}
}
int f = 0;
for (; q.size(); q.pop()) {
int tmp = q.front();
for (auto i : to[tmp]) {
if (!r[i]) {
f = 1;
}
if (r[i]) {
if (!dis[r[i]]) {
dis[r[i]] = dis[tmp] + 1;
q.push(r[i]);
}
}
}
}
return f;
}
void mxf() {
for (; BFS();) {
for (int i = 1; i <= n; i++) {
if (!t[i] && DFS(i)) {
ans++;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u >> v;
to[v].push_back(u);
}
mxf();
for (int i = 1; i <= n; i++) {
if (!t[i]) {
cout << i << ' ';
for (int j = r[i]; j; j = r[j]) {
cout << j << ' ';
}
cout << '\n';
}
}
cout << n - ans << '\n';
return 0;
}
|
Codeforces 1404E Bricks
用一些
的砖精确覆盖一个
的网格,砖可以旋转,其中有一些格子不能覆盖。
解法
考虑最终的方案是如何构成的:
先在所有能覆盖的网格上全部铺上
的砖。对于一个
的砖,可以由同一行的
个连续的
砖依次「行合并」形成。同理,对于一个
的砖。可以由同一列的
个连续的
砖依次「列合并」形成。
显然,一次行合并和一次列合并不能干涉到同一个砖,而且合并的次数越多,砖块数量越少。于是,可以以行合并作为左部点,列合并作为右部点,以前面的冲突作为边,建出一个二分图。随即原问题变成了一个二分图最大独立集问题。
代码
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 | #include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m, belr[220][220], beld[220][220], dcnt, rcnt, vis[100010], dis[100010],
t[100010], r[100010], cnt;
char c[220][220];
vector<int> to[100010];
queue<int> q;
int DFS(int x) {
if (vis[x]) {
return 0;
}
vis[x] = 1;
for (auto i : to[x]) {
if (!r[i]) {
r[i] = x;
t[x] = i;
return 1;
}
if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
r[i] = x;
t[x] = i;
return 1;
}
}
return 0;
}
int BFS() {
fill(vis + 1, vis + rcnt + 1, 0);
fill(dis + 1, dis + rcnt + 1, 0);
for (int i = 1; i <= rcnt; i++) {
if (!t[i]) {
q.push(i);
dis[i] = 1;
}
}
int f = 0;
for (; q.size(); q.pop()) {
int tmp = q.front();
for (auto i : to[tmp]) {
if (!r[i]) {
f = 1;
}
if (r[i]) {
if (!dis[r[i]]) {
dis[r[i]] = dis[tmp] + 1;
q.push(r[i]);
}
}
}
}
return f;
}
int solve() {
int rt = 0;
for (; BFS();) {
for (int i = 1; i <= rcnt; i++) {
if (!t[i] && DFS(i)) {
rt++;
}
}
}
return rt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (c[i][j] == '#') {
cnt++;
if (c[i + 1][j] == '#') {
beld[i][j] = ++dcnt;
}
if (c[i][j + 1] == '#') {
belr[i][j] = ++rcnt;
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (c[i][j] == '#') {
if (c[i - 1][j] == '#' && c[i][j - 1] == '#') {
to[belr[i][j - 1]].push_back(beld[i - 1][j]);
}
if (c[i + 1][j] == '#' && c[i][j + 1] == '#') {
to[belr[i][j]].push_back(beld[i][j]);
}
if (c[i + 1][j] == '#' && c[i][j - 1] == '#') {
to[belr[i][j - 1]].push_back(beld[i][j]);
}
if (c[i - 1][j] == '#' && c[i][j + 1] == '#') {
to[belr[i][j]].push_back(beld[i - 1][j]);
}
}
}
}
cout << cnt - rcnt - dcnt + solve() << '\n';
return 0;
}
|
Codeforces 1139E - Maximize Mex
有
个共有
个元素的可重集,每一次从某一个可重集里面删除一个元素,然后查询「在每一个可重集里面选至多一个元素,可以达到的最大
」。
解法
先考虑如果没有删除元素时怎么做。
对于每一个多重集,开一个新点;对于每一个可能的答案,开一个新点。然后,对于某一个对应点
的多重集的一个元素
,连一条
至
的边。此时这个弱化版本变成了一个二分图最大匹配。
现在加回来删除元素的操作,发现根本搞不了:删了一条边可能引起匹配的巨变,复杂度无法接受。于是,不如反过来,我们每一次加一条边,然后顺过去重新增广。所以本题只能使用匈牙利算法。
代码
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 <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct node {
int u, v;
} arr[5050];
int n, m, t[5050], r[5050], d, ot[5050], kil[5050], vis[5050], ans, out[5050];
vector<int> to[5050];
int DFS(int x) {
if (vis[x]) {
return 0;
}
vis[x] = 1;
for (auto i : to[x]) {
if (r[i] == -1) {
r[i] = x;
t[x] = i;
return 1;
}
if (DFS(r[i])) {
r[i] = x;
t[x] = i;
return 1;
}
}
return 0;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> arr[i].u;
if (arr[i].u > m) {
arr[i].u = m + 1;
}
}
for (int i = 1; i <= n; i++) {
cin >> arr[i].v;
}
cin >> d;
for (int i = 1; i <= d; i++) {
cin >> ot[i];
kil[ot[i]] = 1;
}
for (int i = 1; i <= n; i++) {
if (!kil[i]) {
to[arr[i].u].push_back(arr[i].v);
}
}
fill(r + 1, r + m + 1, -1);
for (; ans <= m;) {
fill(vis, vis + m + 2, 0);
if (DFS(ans)) {
ans++;
} else {
break;
}
}
out[d] = ans;
for (int i = d; i > 1; i--) {
to[arr[ot[i]].u].push_back(arr[ot[i]].v);
for (; ans <= m;) {
fill(vis, vis + m + 2, 0);
if (DFS(ans)) {
ans++;
} else {
break;
}
}
out[i - 1] = ans;
}
for (int i = 1; i <= d; i++) {
cout << out[i] << '\n';
}
return 0;
}
|
通过对原图黑白染色转化成二分图解决问题
洛谷 P3355 - 骑士共存问题
有一个
的国际象棋棋盘,其中一些位置不能放棋子,问最多可以放多少个马使得这些马不会互相攻击。
解法
可以发现,如果对整个棋盘染色使得所有黑格、白格均不相邻,那么马只能够攻击到与其异色的格子。
然后就可以直接二分图最大独立集了。
代码
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 | #include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int kD[8][2] = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
{2, 1}, {1, 2}, {-1, 2}, {-2, 1}};
int n, m, ib;
int vis[200020], dis[200020], t[200020], r[200020], ans, u, v, cnta,
x[220][220], cl[220][220], idx, bel[220][220];
vector<int> to[200020];
queue<int> q;
int DFS(int x) {
if (vis[x]) {
return false;
}
vis[x] = true;
for (auto i : to[x]) {
if (!r[i]) {
r[i] = x;
t[x] = i;
return true;
}
if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
r[i] = x;
t[x] = i;
return true;
}
}
return false;
}
int BFS() {
fill(vis + 1, vis + cnta + 1, false);
fill(dis + 1, dis + cnta + 1, 0);
for (int i = 1; i <= cnta; i++) {
if (!t[i]) {
q.push(i);
dis[i] = 1;
}
}
int f = 0;
for (; q.size(); q.pop()) {
int tmp = q.front();
for (auto i : to[tmp]) {
if (!r[i]) {
f = 1;
}
if (r[i]) {
if (!dis[r[i]]) {
dis[r[i]] = dis[tmp] + 1;
q.push(r[i]);
}
}
}
}
return f;
}
void din() {
for (; BFS();) {
for (int i = 1; i <= cnta; i++) {
if (!t[i] && DFS(i)) {
ans++;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u >> v;
x[u][v] = true;
}
cl[1][1] = 1;
if (!x[1][1]) {
bel[1][1] = ++idx;
}
for (int i = 2; i <= n; i++) {
cl[1][i] = cl[1][i - 1] ^ 1;
if (!x[1][i] && cl[1][i]) {
bel[1][i] = ++idx;
} else {
if (!x[1][i]) {
bel[1][i] = ++ib;
}
}
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cl[i][j] = cl[i - 1][j] ^ 1;
if (!x[i][j] && cl[i][j]) {
bel[i][j] = ++idx;
} else {
if (!x[i][j]) {
bel[i][j] = ++ib;
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (!x[i][j]) {
cnta += cl[i][j];
for (int k = 0; k < 8; k++) {
if (i + kD[k][0] > 0 && j + kD[k][1] > 0 &&
bel[i + kD[k][0]][j + kD[k][1]] &&
!x[i + kD[k][0]][j + kD[k][1]]) {
if (cl[i + kD[k][0]][j + kD[k][1]]) {
to[bel[i + kD[k][0]][j + kD[k][1]]].push_back(bel[i][j]);
} else {
to[bel[i][j]].push_back(bel[i + kD[k][0]][j + kD[k][1]]);
}
}
}
}
}
}
din();
cout << n * n - m - ans << '\n';
return 0;
}
|
习题
参考资料
- http://www.matrix67.com/blog/archives/116
本页面最近更新:2025/6/3 22:39:38,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:5ab-juruo, Chrogeek, countercurrent-time, Enter-tainer, H-J-Granger, Henry-ZHR, hhc0001, ksyx, StudyingFather, thallium, william-song-shy, 310552025atNYCU, accelsao, billchenchina, c-forrest, CCXXXI, Early0v0, Great-designer, Haohu Shen, HeRaNO, iamtwz, NachtgeistW, ouuan, SukkaW, TianKong-y, Tiphereth-A, Xeonacid, XiaoQuQuSD
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用