P9879 Check Pattern is Good 题解
继续加训网络流。
一看就是非常典型的集合划分模型，考虑转化成最小割模型。
但是你注意到直接做可能并不是很好做，因为对颜色的要求和方位有关。
我们先考虑最优情况是什么，显然就是黑白染色，这样每个
此时如果改变一个格子的颜色，就会使答案减少
因此我们用这种方式建图：
- 对于每个格子建出一个点
，对于每个 的方格建出一个点 表示是否都划分到不改变/改变的集合。 - 对于那些已经钦定了颜色的格子，根据其指定的颜色是否和黑白染色后的颜色相同，如果相同则从
到 连一条 的边表示一定不能改变颜色。不同则连一条到 容量为 的边表示一定要改变颜色。 向每个 连一跳容量为 的边，并且 向 连一条容量为 的边。这样如果四个格子中的任意一个被划分到了改变的集合， 到 的边就会成为正向割边，产生 的代价。 向 连一条容量为 的边，并且 向 连一条容量为 的边。这样如果四个格子中的任意一个被划分到不变的集合， 到 的边就会成为正向割边并产生 的代价。
最后算出来最小割之后用
考虑分析复杂度。显然流量最多
注意到，所有
输出方案可以直接先把确定的都填上，然后从 ? 位置填上和黑白染色时相反的颜色即可。
参考代码： 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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304#include <array>
#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
using uint = unsigned int;
namespace numbers {
template <typename T>
T inf() {
assert(false);
}
template <>
int inf<int>() {
return 0x3f3f3f3f;
}
template <>
uint inf<uint>() {
return 0x3f3f3f3f;
}
} // namespace numbers
namespace solve {
namespace network {
struct edge {
uint src, dest;
uint vol;
};
namespace g {
using std::vector;
struct node {
edge val;
uint nxt;
};
static const uint npos = static_cast<uint>(-1);
vector<uint> head;
std::array<node, 100 * 100 * 50> nd;
uint nxt_pos;
void init(uint n) {
head.resize(n);
std::fill(head.begin(), head.end(), npos);
nxt_pos = 0;
}
void insert(uint pos, const edge &_val) {
nd[nxt_pos++] = node{_val, head[pos]};
head[pos] = nxt_pos - 1;
}
void insert(uint pos, edge &&_val) {
nd[nxt_pos++] = node{_val, head[pos]};
head[pos] = nxt_pos - 1;
}
uint next_pos(uint i) { return nd[i].nxt; }
} // namespace g
uint s, t;
uint n;
std::vector<uint> dis;
std::vector<uint> cur;
bool bfs() {
std::fill(dis.begin(), dis.end(), numbers::inf<uint>());
std::vector<bool> vis(n);
std::queue<uint> q;
q.push(s);
vis[s] = true;
dis[s] = 0;
while (!q.empty()) {
auto f = q.front();
q.pop();
for (uint i = g::head[f]; i != g::npos; i = g::next_pos(i)) {
const edge &e = g::nd[i].val;
if (!vis[e.dest] && e.vol != 0) {
dis[e.dest] = dis[f] + 1;
vis[e.dest] = true;
q.push(e.dest);
}
}
}
cur = g::head;
return dis[t] != numbers::inf<uint>();
}
uint dfs(uint p, uint max_flow) {
if (p == t || !max_flow) {
return max_flow;
}
uint final_flow = 0;
for (; cur[p] != g::npos; cur[p] = g::next_pos(cur[p])) {
const auto &i = cur[p];
const edge &e = g::nd[i].val;
if (dis[e.dest] != dis[p] + 1) {
continue;
}
if (e.vol == 0) {
continue;
}
auto r = dfs(e.dest, std::min(e.vol, max_flow));
g::nd[i].val.vol -= r;
g::nd[i ^ 1].val.vol += r;
final_flow += r;
max_flow -= r;
if (!max_flow) {
break;
}
}
return final_flow;
}
uint dinic() {
uint r = 0;
while (bfs()) {
r += dfs(s, numbers::inf<uint>());
}
return r;
}
void init(uint _n, uint _s, uint _t) {
n = _n;
s = _s;
t = _t;
dis.resize(n);
cur.resize(n);
g::init(n);
}
void add_edge(uint src, uint dest, uint vol) {
g::insert(src, {src, dest, vol});
g::insert(dest, {dest, src, 0});
}
} // namespace network
uint n, m;
uint index_pattern(uint i, uint j, bool chagne) {
return (i * (m - 1) + j) * 2 + chagne + 1;
}
void solve() {
std::cin >> n >> m;
std::vector<std::string> mp(n, std::string(m, '?'));
network::init((n - 1) * (m - 1) * 2 + 2, 0, (n - 1) * (m - 1) * 2 + 1);
std::vector<bool> invaild(network::n);
for (uint i = 0; i < n; i++) {
std::cin >> mp[i];
for (uint j = 0; j < m; j++) {
if (mp[i][j] == '?') {
continue;
/**
* 连两条割开代价为 0 的边。
*
* 没啥用。
*/
}
bool b = mp[i][j] == 'B';
bool real = (i + j) & 1;
const std::array<std::array<int, 2>, 4> mv{
std::array<int, 2>{-1, 0},
std::array<int, 2>{0, -1},
std::array<int, 2>{0, 0},
std::array<int, 2>{-1, -1},
};
for (uint k = 0; k < 4; k++) {
uint new_i = i + mv[k][0], new_j = j + mv[k][1];
if (new_i >= n - 1 || new_j >= m - 1) {
continue;
}
if (b == real) {
invaild[index_pattern(new_i, new_j, 1)] = true;
}
else {
invaild[index_pattern(new_i, new_j, 0)] = true;
}
}
}
}
uint cnt = (n - 1) * (m - 1) * 2;
for (uint i = 0; i < n - 1; i++) {
for (uint j = 0; j < m - 1; j++) {
for (uint k = 0; k < 2; k++) {
if (invaild[index_pattern(i, j, k)]) {
cnt--;
}
}
}
}
for (uint i = 0; i < n - 1; i++) {
for (uint j = 0; j < m - 1; j++) {
if (!invaild[index_pattern(i, j, 0)]) {
network::add_edge(network::s, index_pattern(i, j, 0), 1);
}
if (!invaild[index_pattern(i, j, 1)]) {
network::add_edge(index_pattern(i, j, 1), network::t, 1);
}
/**
* 直接割掉对应的边就行了。
*/
/**
* 中间那层的边完全没用。
*
* 直接左向右侧连边即可。
*/
const std::array<std::array<int, 2>, 9> mv{
std::array<int, 2>{-1, 0}, std::array<int, 2>{+1, 0},
std::array<int, 2>{0, -1}, std::array<int, 2>{0, +1},
std::array<int, 2>{0, 0}, std::array<int, 2>{-1, -1},
std::array<int, 2>{-1, +1}, std::array<int, 2>{+1, -1},
std::array<int, 2>{+1, +1},
};
for (uint k = 0; k < 9; k++) {
uint new_i = i + mv[k][0], new_j = j + mv[k][1];
if (new_i >= n - 1 || new_j >= m - 1) {
continue;
}
if (invaild[index_pattern(i, j, 0)] ||
invaild[index_pattern(new_i, new_j, 1)]) {
continue;
}
network::add_edge(index_pattern(i, j, 0),
index_pattern(new_i, new_j, 1), 1);
}
}
}
/**
* 和 S 相连是保持不变，和 T 是变。
*/
std::cout << cnt - network::dinic() << "\n";
std::vector<std::string> ans(mp);
for (uint i = 0; i < n - 1; i++) {
for (uint j = 0; j < m - 1; j++) {
if (network::dis[index_pattern(i, j, 0)] !=
numbers::inf<uint>()) {
/**
* 源点不可达。
*
* 划分至 T。修改。
*/
ans[i][j] = ((i + j) & 1) ? 'B' : 'W';
ans[i][j + 1] = ((i + j + 1) & 1) ? 'B' : 'W';
ans[i + 1][j] = ((i + j + 1) & 1) ? 'B' : 'W';
ans[i + 1][j + 1] = ((i + j) & 1) ? 'B' : 'W';
}
}
}
for (uint i = 0; i < n; i++) {
for (uint j = 0; j < m; j++) {
if (ans[i][j] == '?') {
if (mp[i][j] == '?') {
ans[i][j] = !((i + j) & 1) ? 'B' : 'W';
}
}
}
}
for (uint i = 0; i < n; i++) {
std::cout << ans[i] << "\n";
}
return;
}
} // namespace solve
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
uint t;
std::cin >> t;
while (t--) {
solve::solve();
}
std::cout << std::flush;
return 0;
}