CF1592F2 Alice and Recoloring 2

题意

给定一个矩阵，有两种颜色 \(W\) 和 \(B\)。

你可以花 \(1\) 的代价反转一个包含 \((1, 1)\) 的矩阵。
你可以花 \(3\) 的代价反转一个包含 \((n, 1)\) 的矩阵。
你可以花 \(4\) 的代价反转一个包含 \((1, m)\) 的矩阵。
你可以花 \(2\) 的代价反转一个包含 \((n, m)\) 的矩阵。

Sol

显然中间两种操作是消愁。直接不管。

考虑将 \(B\) 看为 \(1\)，\(W\) 看为 \(0\)。

对矩阵倒着做前缀和。

\(1\) 操作变为在前缀和数组上操作一个点。

\(4\) 操作变为在前缀和数组上操作四个点。

不难发现对于同样的一列或者一行，只可能进行一次 \(4\) 操作。

注意到进行一次 \(4\) 操作当且仅当 \((x, y) = 1\)，\((x, m) = 1\)，\((n, y) = 1\)。

直接把每一行，每一列看成 \(n + m\) 个点。

对于第一条限制，建二分图，按照第二条限制连边跑二分图最大匹配即可。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <queue>
#define int long long
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
string read_() {
	string ans;
	char c = getchar();
	while (c != 'W' && c != 'B')
		c = getchar();
	while (c == 'W' || c == 'B') {
		ans += c;
		c = getchar();
	}
	return ans;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

#define fi first
#define se second

const int N = 1e3 + 5, M = 1e6 + 5, inf = 2e18;

namespace G {

array <int, N> fir;
array <int, M> nex, to, cap;
int cnt = 1;
void add(int x, int y, int z) {
	cnt++;
	nex[cnt] = fir[x];
	to[cnt] = y;
	cap[cnt] = z;
	fir[x] = cnt;
}
void _add(int x, int y, int z) {
	add(x, y, z);
	add(y, x, 0);
}

}

namespace Mfl {

array <int, N> dis, cur;
queue <int> q;

bool bfs(pii st) {
	dis.fill(-1), dis[st.fi] = 0;
	q.push(st.fi);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = G::fir[u]; i; i = G::nex[i]) {
			if (!G::cap[i] || ~dis[G::to[i]]) continue;
			dis[G::to[i]] = dis[u] + 1, q.push(G::to[i]);
		}
	}
	return ~dis[st.se];
}

int dfs(int x, int augcd, pii st) {
	if (x == st.se) return augcd;
	int augc = augcd;
	for (int &i = cur[x]; i; i = G::nex[i]) {
		if (!G::cap[i] || dis[G::to[i]] <= dis[x]) continue;
		int flow = dfs(G::to[i], min(augc, G::cap[i]), st);
		augc -= flow;
		G::cap[i] -= flow, G::cap[i ^ 1] += flow;
		if (!augc) break;
	}
	return augcd - augc;
}

int dinic(pii st) {
	int ans = 0;
	while (bfs(st)) {
		copy(G::fir.begin(), G::fir.end(), cur.begin());
		ans += dfs(st.fi, inf, st);
	}
	return ans;
}

}

string mp[N];

array <array <int, N>, N> s;

signed main() {
	int n = read(), m = read();
	for (int i = 1; i <= n; i++)
		mp[i] = " " + read_();
	for (int i = n; i; i--)
		for (int j = m; j; j--)
			s[i][j] = (mp[i][j] == 'B') ^
					(mp[i + 1][j] == 'B') ^
					(mp[i][j + 1] == 'B') ^
					(mp[i + 1][j + 1] == 'B');
	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++)
			if (s[i][j] && s[i][m] && s[n][j])
				G::_add(i, j + n, 1);
	pii st = make_pair(n + m, n + m + 1);
	for (int i = 1; i < n; i++) G::_add(st.fi, i, 1);
	for (int i = 1; i < m; i++) G::_add(i + n, st.se, 1);
	int k = Mfl::dinic(st), ans = 0;
	s[n][m] ^= (k & 1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			ans += s[i][j];
	write(ans - k), puts("");
	return 0;
}