有一张 (n imes m) 的方格图，初始全白，目标状态给定。
有 4 种操作（反转的意思是黑 ( o) 白，白 ( o) 黑）：
- 反转一个包含 ((1, 1)) 的子矩形，花费 (1)。
- 反转一个包含 ((n, 1)) 的子矩形，花费 (3)。
- 反转一个包含 ((1, m)) 的子矩形，花费 (4)。
- 反转一个包含 ((n, m)) 的子矩形，花费 (2)。
求达成目标状态的最小花费。
(1 le n, m le 500)。
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 imes 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) 即可。答案为 ( extit{rem} - k)。( extit{rem}) 表示剩下的 (1) 的个数。
我使用的是 dinic 求二分图最大匹配，时间复杂度为 (O(n^2 sqrt{n}))。
#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
", ans);
return 0;
}