复习一下最小割。
考虑翻转横纵坐标和为奇数的颜色,那么就变成了,相邻两个格子,相同颜色产生 \(1\) 的贡献。
一眼 P4313 文理分科。每个格子被分到 \(S\) 表示染黑,分到 \(T\) 表示染白。对于每两个相邻格子,建两个虚点,分别表示它们都染黑或者都染白的情况。
最后跑一下最小割。
code
// Problem: F - Zebraness
// Contest: AtCoder - Caddi Programming Contest 2021(AtCoder Beginner Contest 193)
// URL: https://atcoder.jp/contests/abc193/tasks/abc193_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
const int maxm = 1000100;
const int inf = 0x3f3f3f3f;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int n, ntot, head[maxm], len = 1, S, T, id[maxn][maxn];
char s[maxn][maxn];
struct edge {
int to, next, cap, flow;
} edges[maxm];
inline void add_edge(int u, int v, int c, int f) {
edges[++len].to = v;
edges[len].next = head[u];
edges[len].cap = c;
edges[len].flow = f;
head[u] = len;
}
struct Dinic {
int d[maxm], cur[maxm];
bool vis[maxm];
inline void add(int u, int v, int c) {
add_edge(u, v, c, 0);
add_edge(v, u, 0, 0);
}
inline bool bfs() {
for (int i = 1; i <= ntot; ++i) {
vis[i] = 0;
d[i] = -1;
}
queue<int> q;
q.push(S);
vis[S] = 1;
d[S] = 0;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[u] + 1;
q.push(e.to);
}
}
}
return vis[T];
}
int dfs(int u, int a) {
if (u == T || !a) {
return a;
}
int flow = 0, f;
for (int &i = cur[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[i ^ 1].flow -= f;
flow += f;
a -= f;
if (!a) {
break;
}
}
}
return flow;
}
inline int solve() {
int flow = 0;
while (bfs()) {
for (int i = 1; i <= ntot; ++i) {
cur[i] = head[i];
}
flow += dfs(S, inf);
}
return flow;
}
} solver;
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
for (int j = 1; j <= n; ++j) {
id[i][j] = ++ntot;
if (s[i][j] != '?' && ((i + j) & 1)) {
s[i][j] = (s[i][j] == 'B' ? 'W' : 'B');
}
}
}
S = ++ntot;
T = ++ntot;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i][j] == 'B') {
solver.add(S, id[i][j], inf);
} else if (s[i][j] == 'W') {
solver.add(id[i][j], T, inf);
}
}
}
int s = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if ((i + j) & 1) {
continue;
}
for (int k = 0; k < 4; ++k) {
int nx = i + dx[k], ny = j + dy[k];
if (nx < 1 || nx > n || ny < 1 || ny > n) {
continue;
}
int u = ++ntot;
solver.add(S, u, 1);
solver.add(u, id[i][j], inf);
solver.add(u, id[nx][ny], inf);
u = ++ntot;
solver.add(u, T, 1);
solver.add(id[i][j], u, inf);
solver.add(id[nx][ny], u, inf);
s += 2;
}
}
}
printf("%d\n", s - solver.solve());
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Zebraness Beginner AtCoder Contest 193zebraness beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 310