F - Zebraness(最小割)

F - Zebraness(最小割)

題意

給定

n

×

n

n\times n

n×n矩陣，每個格子為

B

,

W

B,W

B,W或者？，？可以填任意顔色。求最大相鄰格子不同色的對數。

思路

最小割問題，但是不同色有貢獻不能轉化為該問題，是以我們需要轉換一下題目，也就是該為同色加分，如何轉換，隻需把

(

i

+

j

)

(i+j)

(i+j)為奇數的格子全部翻轉即可，這樣原來加分的對數就不會加分，原來不會加分的對數就會加分。

是以可以用最小割。

圖形化一下：

代碼

// 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;
}