题解 CF1592F2 【Alice and Recoloring 2】
syksykCCC
·
·
题解
有一张 n \times m 的方格图，初始全白，目标状态给定。
有 4 种操作（反转的意思是黑 \to 白，白 \to 黑）：
- 反转一个包含 (1, 1) 的子矩形，花费 1。
- 反转一个包含 (n, 1) 的子矩形，花费 3。
- 反转一个包含 (1, m) 的子矩形，花费 4。
- 反转一个包含 (n, m) 的子矩形，花费 2。
求达成目标状态的最小花费。
2s, 256MB
---
**引理 1**：第 2 和第 3 种操作不会用到。
> **证明**：考虑到不管是第 2 种还是第 3 种操作，都可以用两次第 1 种操作代替，而且代价显然更优。所以永远不会使用第 2 和第 3 种操作。
现在的问题就转化为了只存在第 1 和第 4 种操作的情况了。
将目标状态与初始状态对换，即给定一个初始有黑白两色的方格图，花最小的代价使得全部变成白色。
矩形反转显然是不好处理的，考虑弄一个类似前缀和的东西来优化掉。
将黑色视为 $1$，白色视为 $0$。构造一个数组 $a$，其中 $a_{i, j} = s_{i, j} \oplus s_{i + 1, j} \oplus s_{i, j + 1} \oplus s_{i + 1, j + 1}$（超出网格的部分默认是白色）。
非常显然，当 $a$ 数组全部变为 $0$ 时，$s$ 数组也就全部变为了 $0$。
观察 1, 4 两种操作对 $a$ 数组的影响，发现是：
* 对于第 1 种操作，只会有 1 个格子的 $a$ 发生了反转。
* 对于第 4 种操作，会有 4 个格子的 $a$ 发生反转，且这 4 个格子形如 $(x, y)$，$(n, y)$，$(x, m)$，$(n, m)$。记这样的操作为 $op(x, y)$。
**引理 2**：不会同时使用 $op(x, y_1)$ 和 $op(x, y_2)$。同理不会同时使用 $op(x_1, y)$ 和 $op(x_2, y)$。
> **证明**：以前一种为例，$(n, m)$ 和 $(x, m)$ 都被反转了两次，所以不会发生改变。那么也就是花费了 $4$ 的代价来反转了 $2\times 2=4$ 个格子。这显然可以被第 1 种操作代替。
**引理 3**：除非 $(x, y)$，$(n, y)$ 和 $(x, m)$ 都为 $1$，才会使用 $op(x, y)$。
> **证明**：如果这中间有一个不为 $1$，那么这次操作就产生了一个错误的反转。为了达成最终目标，显然会使用一次第 1 种操作把它反转回来（注：不会是另一个第 4 种操作，根据引理 2 可以得知）。那么仅仅是反转了另外 3 个格子，代价都至少为 $1 + 2 = 3$，完全可以使用第 1 种操作代替。
于是就可以做题了，建立一个二分图，左部有 $n - 1$ 个点代表行，右部有 $m - 1$ 个点代表列。
对于 $(x, y)$，如果它满足引理 3 的条件，则把左部的 $x$ 和右部的 $y$ 连边。
求这个二分图的最大匹配数 $k$ 即可。答案为 $\textit{rem} - k$。$\textit{rem}$ 表示剩下的 $1$ 的个数。
我使用的是 dinic 求二分图最大匹配，时间复杂度为 $O(n^2 \sqrt{n})$。
```cpp
#include <bits/stdc++.h>
const int N = 505;
char str[N][N];
int n, m, cnt = -1, a[N][N], h[N << 1], S, T;
struct edge {
int v, w, nxt;
} e[N * N * 2];
void add_edge(int u, int v) {
e[++cnt] = (edge){v, 1, h[u]}; h[u] = cnt;
e[++cnt] = (edge){u, 0, h[v]}; h[v] = cnt;
}
int que[N << 1], hd, tl, lev[N << 1];
bool bfs() {
memset(lev, 0, sizeof(lev));
hd = tl = lev[S] = 1; que[1] = S;
while(hd <= tl) {
int u = que[hd++];
for(int i = h[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(!lev[v] && e[i].w > 0) {
que[++tl] = v;
lev[v] = lev[u] + 1;
}
}
}
return lev[T];
}
int cur[N << 1];
int dfs(int u, int can_flow) {
if(u == T) return can_flow;
int res_flow = 0;
for(int &i = cur[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(lev[v] == lev[u] + 1 && e[i].w > 0) {
int will_flow = dfs(v, std::min(can_flow, e[i].w));
res_flow += will_flow;
can_flow -= will_flow;
e[i ^ 1].w += will_flow;
e[i].w -= will_flow;
if(!can_flow) break;
}
}
if(!res_flow) lev[u] = 0;
return res_flow;
}
int dinic() {
int res = 0;
while(bfs()) {
memcpy(cur, h, sizeof(h));
res += dfs(S, INT_MAX);
}
return res;
}
int main() {
memset(h, -1, sizeof(h));
scanf("%d %d", &n, &m);
S = n + m + 1; T = n + m + 2;
for(int i = 1; i <= n; i++) {
scanf("%s", str[i] + 1);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
a[i][j] = (str[i][j] == 'B') ^ (str[i][j + 1] == 'B') ^ (str[i + 1][j] == 'B') ^ (str[i + 1][j + 1] == 'B');
}
}
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) {
if(a[i][j] && a[n][j] && a[i][m]) {
add_edge(i, j + n);
}
}
}
for(int i = 1; i < n; i++) add_edge(S, i);
for(int j = 1; j < m; j++) add_edge(j + n, T);
int k = dinic(), ans = 0;
a[n][m] ^= (k & 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
ans += a[i][j];
}
}
ans -= k;
printf("%d\n", ans);
return 0;
}
```