Caddi Programming Contest 2021(AtCoder Beginner Contest 193) F.Zebraness(最小割)_[abc193f] zebraness 题解

题目

一个n*n(n<=100)的网格图，只由'B'、'W'、'?'三种字符构成，'?'表示你填'B'或'W'都可以

现在要确定填?的方案，使得这张网格图中相邻的异色对对数最大

对于(i,j)，认为它和(i+1,j)、(i-1,j)、(i,j-1)、(i,j+1)相邻

思路来源

官方题解：https://atcoder.jp/contests/abc193/editorial/817

题解

最大化异色对对数，即最小化同色对对数x，则答案为2*n(n-1)-x

最小化一个值，且网格图，且只有黑白两色，于是想到最小割，

对于相邻的对数来说，BB或WW是要被割掉的边，权值为1的无向边

BB或者WW这种连边方式无法连边，考虑对(i+j)&1的颜色进行取反

这样，就是相邻BW是要被割掉的边，构成了两个集合

B或W是点，是不能被割掉的，设置割掉的代价为INF，

令一个连超级源点ss，一个连超级汇点ee，

由于这道题的限制，每个点的流量最大为4，所以INF=4即可

至于问号为什么不用管，

考虑问号出现在一条BW的路径上的时候，大概是B？W的形式，

割掉B？代表设置?为B，反之割掉？W代表设置为W，再按(i+j)&1搞回去即映射回一种方案

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map> 
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=1e4+10;
const int maxm=1e5+10;
int level[maxn];
int head[maxn],cnt;
int ss,ee;
struct edge{int v,nex;ll w;}e[maxm];
void init()
{
	cnt=0;
	memset(head,-1,sizeof head);
}
void add(int u,int v,ll w)
{
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
void add2(int u,int v,ll w,bool op)//是否为有向图 
{
	add(u,v,w);
	add(v,u,op?0:w);
}
bool bfs(int s,int t)
{
	queue<int>q;
	memset(level,0,sizeof level);
	level[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		if(x==t)return 1;
		for(int u=head[x];~u;u=e[u].nex)
		{
			int v=e[u].v;ll w=e[u].w;
			if(!level[v]&&w)
			{
				level[v]=level[x]+1;
				q.push(v);
			}
		}
	}
	return 0;
}
ll dfs(int u,ll maxf,int t)
{
	if(u==t)return maxf;
	ll ret=0;
	for(int i=head[u];~i;i=e[i].nex)
	{
		int v=e[i].v;ll w=e[i].w;
		if(level[u]+1==level[v]&&w)
		{
			ll MIN=min(maxf-ret,w);
			w=dfs(v,MIN,t);
			e[i].w-=w;
			e[i^1].w+=w;
			ret+=w;
			if(ret==maxf)break;
		}
	}
	if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了 
	return ret;
}
ll Dinic(int s,int t)
{
	ll ans=0;
	while(bfs(s,t))
	ans+=dfs(s,INF,t);
	return ans;
}
char s[105][105];
int n;
int f(int x,int y)
{
    return x*n+y;
}
int main()
{
    init();
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        scanf("%s",s[i]);
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
           if(s[i][j]=='?')continue;
           if((i+j)&1)
           {
               s[i][j]^='B'^'W';
           }
        }
    }
    ss=n*n+1,ee=n*n+2;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(j+1<n)add2(f(i,j),f(i,j+1),1,0);
            if(i+1<n)add2(f(i,j),f(i+1,j),1,0);
            if(s[i][j]=='B')add2(ss,f(i,j),4,1);
            if(s[i][j]=='W')add2(f(i,j),ee,4,1);
        }
    }
    printf("%lld\n",2ll*n*(n-1)-Dinic(ss,ee));
    return 0;
}