F - Zebraness(最小割)
题意
给定
n
×
n
n\times n
n×n矩阵,每个格子为
B
,
W
B,W
B,W或者?,?可以填任意颜色。求最大相邻格子不同色的对数。
思路
最小割问题,但是不同色有贡献不能转化为该问题,所以我们需要转换一下题目,也就是该为同色加分,如何转换,只需把
(
i
+
j
)
(i+j)
(i+j)为奇数的格子全部翻转即可,这样原来加分的对数就不会加分,原来不会加分的对数就会加分。
因此可以用最小割。
图形化一下:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5CMzIzN0QzMhNDOwQDZhV2YxYzXwAjMxUTMxMzLcJTMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
代码
// 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
// Date: 2021-03-02 12:21:08
// --------by Herio--------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=105,M=5e5+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
int n,st,ed,tot;
int id(int x,int y){
return (x-1)*n+y;
}
struct edge{
int to,nt,w;
}e[M];
int h[N*N],cur[N*N],cnt=1,dep[N*N];
void add(int u,int v,int w){
e[++cnt]={v,h[u],w},h[u]=cnt;
e[++cnt]={u,h[v],0},h[v]=cnt;
}
int dfs(int u,int c){
if(u==ed) return c;
int res=c;
for(int &i=cur[u];i;i=e[i].nt){
int v=e[i].to,w=e[i].w;
if(w&&dep[v]==dep[u]+1){
int now=dfs(v,min(res,w));
if(!now) dep[v]=1;//如果剩余路径的最大流为0,说明该点不用再遍历了.
else e[i].w-=now,e[i^1].w+=now,res-=now;
}
if(!res) return c;//如果剩余流量为0,说明最大流不能再更大了,直接返回.
}return c-res;
}
bool bfs(){
queue<int>q;q.push(st);mst(dep,0),dep[st]=1;
while(!q.empty()){
int u=q.front();q.pop();cur[u]=h[u];//初始化
for(int i=h[u];i;i=e[i].nt){
int v=e[i].to,w=e[i].w;
if(w&&!dep[v]) dep[v]=dep[u]+1,q.push(v);
}
}return dep[ed];
}
ll dinic(){
ll s=0;
while(bfs()) s+=dfs(st,inf);
return s;
}
char a[N][N];
int main(){
scanf("%d",&n);
st=0,ed=n*n+1;
for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(a[i][j]=='?') continue;
if((i+j)&1) a[i][j]=(a[i][j]=='B')?'W':'B';
if(a[i][j]=='B') add(st,id(i,j),inf);
else add(id(i,j),ed,inf);
}
for(int i=1;i<n;i++)
for(int j=1;j<=n;j++)
add(id(i,j),id(i+1,j),1),add(id(i+1,j),id(i,j),1);
for(int i=1;i<=n;i++)
for(int j=1;j<n;j++)
add(id(i,j),id(i,j+1),1),add(id(i,j+1),id(i,j),1);
printf("%lld\n",2*n*(n-1)-dinic());
return 0;
}