loj 6226. 「网络流 24 题」骑士共存问题

1. 题目链接#

[loj 6226. 「网络流 24 题」骑士共存问题]

2. 题目描述#

Problem Description

3. 解题思路#

题目中要求如果一个顶点被选择,那么8个方向上的顶点就不能被选择。显然,这很像二分图的染色问题。
将每个非障碍的顶点与其8个方向上的非障碍顶点连一条边,那么本题就是一个求最大独立集的问题,而且是一个求二分图的最大独立集的问题。
为什么是二分图呢?可以从下面两条性质来分析:

  • 对于任意节点$u$,不可能经过奇数步回到节点$u$,实际上,这就是 匈牙利算法 Hungary 的进行二分图的判断的主要思想;
  • 按照题目中那个图,将所有顶点划分成红色、黄色两类节点,可以发现同色的节点之间没有边。

而二分图上有很好的性质,比如:

  • 最大匹配数 = 最小点覆盖;
  • 最大独立集 = 最小边覆盖 = 顶点数 $\lvert V \lvert$ - 最大匹配数;
  • DAG 的最小路径覆盖数 = DAG 图中的节点数 - 相应二分图中的最大匹配数。
    • DAG 的最小路径覆盖是指找最小数目的互相不相交的有向路径,满足 DAG 的所有顶点都被覆盖。
    • DAG 对应的二分图这样构造:对于 DAG 中的一个顶点 $p$,二分图中有两个顶点 $p$ 和 $p’$,对应 DAG 中的一条有向边 $p\to q$,二分图中有 $p\to q’$ 的一条无向边。二分图中 $p$ 属于 $S$ 集合,$p’$ 属于 $T$ 集合.
  • ……

求二分图的最大匹配数的方法有 匈牙利算法(复杂度$\mathcal O(VE)$) 和 网络流(代表算法就是Dinic/Hopcroft-carp 算法,复杂度$\mathcal O(\sqrt{V}E)$)。

4. 参考代码#

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

const int MAXN = 205;
const int MX = MAXN * MAXN; // 点数
const int MS = MX * 8 * 2; // 边数
template<class T> struct Max_Flow {
int n;
int Q[MX], sign;
int head[MX], level[MX], cur[MX], pre[MX];
int nxt[MS], pnt[MS], E;
T cap[MS];
void Init(int n) {
E = 0, this->n = n + 1;
fill(head, head + this->n, -1);
}
void Add(int from, int to, T c, T rw = 0) {
pnt[E] = to, cap[E] = c;
nxt[E] = head[from], head[from] = E++;
pnt[E] = from, cap[E] = rw;
nxt[E] = head[to], head[to] = E++;
}
bool BFS(int s, int t) {
sign = t;
fill(level, level + n, -1);
int *front = Q, *tail = Q;
*tail++ = t;
level[t] = 0;
while (front < tail && level[s] == -1) {
int u = *front++;
for (int e = head[u]; e != -1; e = nxt[e]) {
if (cap[e ^ 1] > 0 && level[pnt[e]] < 0) {
level[pnt[e]] = level[u] + 1;
*tail++ = pnt[e];
}
}
}
return level[s] != -1;
}
void Push(int t, T &flow) {
T mi = inf;
for (int p = pre[t]; p != -1; p = pre[pnt[p ^ 1]]) {
mi = min(mi, cap[p]);
}
for (int p = pre[t]; p != -1; p = pre[pnt[p ^ 1]]) {
cap[p] -= mi;
cap[p ^ 1] += mi;
if (!cap[p]) sign = pnt[p ^ 1];
}
flow += mi;
}
void DFS(int u, int t, T &flow) {
if (u == t) {
Push(t, flow);
return;
}
for (int &e = cur[u]; e != -1; e = nxt[e]) {
if (cap[e] > 0 && level[u] - 1 == level[pnt[e]]) {
pre[pnt[e]] = e;
DFS(pnt[e], t, flow);
if (level[sign] > level[u]) return;
}
}
sign = t;
}
T Dinic(int s, int t) {
pre[s] = -1;
T flow = 0;
while (BFS(s, t)) {
copy(head, head + n, cur);
DFS(s, t, flow);
}
return flow;
}
};
Max_Flow<int> mflow;

const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int n, m, src, dst;
vector<bool> flag, used;

void dfs(int x, int y, bool f) {
int u = (x - 1) * n + y;
used[u] = true;
if(!f) mflow.Add(src, u, 1);
else mflow.Add(u, dst, 1);
for(int d = 0; d < 8; ++d) {
int nx = x + dx[d], ny = y + dy[d];
if(nx < 1 || ny < 1 || nx > n || ny > n) continue;
int v = (nx - 1) * n + ny;
if(flag[v]) continue;
if(!f) mflow.Add(u, v, 1);
if(used[v]) continue;
dfs(nx, ny, f ^ 1);
}
}

int main() {
#ifdef __LOCAL_WONZY__
freopen("input.txt", "r", stdin);
#endif
while(~scanf("%d %d", &n, &m)) {
flag = vector<bool>(n * n + 1, false);
for(int i = 1; i <= m; ++i) {
int x, y; scanf("%d %d", &x, &y);
flag[(x - 1) * n + y] = true;
}
src = 0, dst = n * n + 1;
mflow.Init(n * n + 2);
used = vector<bool>(n * n + 1, false);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
int u = (i - 1) * n + j;
if(flag[u] || used[u]) continue;
dfs(i, j, 0);
}
}
int num = 0;
for(int i = 1; i <= n * n; ++i) num += !flag[i];
int mf = mflow.Dinic(src, dst);
cout << num - mf << endl;
}
return 0;
}
用真金白银的方式为你想要的世界投票吧!