【2023NOI模拟赛19】color on board 做题记录

有一个 $n\times m$ 的网格，刚开始每个格子都是白色的，你要把 $(i,j)$ 的颜色通过以下三种方式变为 $a_{i,j}$：

• 涂白横着/竖着排列的若干格子，若涂了 $k$ 格，则代价为 $Ak+B$；
• 涂黑横着/竖着排列的若干格子，若涂了 $k$ 格，则代价为 $Ak+B$；
• 涂黑/涂白单独某个格子，代价为 $C$；

一个格子不能被涂色超过两次，并且一个格子不能被涂白再涂黑。

求最小代价。

$1\le n,m\le 40$，$0\le A,B,C\le 40$，$C\le A+B$。

考虑最小割的本质，设点 $u$ 最终在源点 $S$ 所在的连通块则 $b_u=1$，在汇点 $T$ 所在的连通块则 $b_u=0$，那么：

• 边 $(S,x,a)$ 对答案的贡献为 $a\times (1-b_x)$；
• 边 $(x,T,a)$ 对答案的贡献为 $a\times b_x$；
• 边 $(x,y,a)$ 对答案的贡献为 $a\times b_x(1-b_y)$；

回到本题，考虑涂色的顺序，显然可以分为三步：

• 横竖涂黑
• 横竖涂白
• 单点涂色

确认了第一步和第二步，第三步就可以唯一确定了，那么设：

• $bh_{x,y}$ 为 $[(x,y)\text{ 被横着涂黑}]$；
• $bs_{x,y}$ 为 $[(x,y)\text{ 未被竖着涂黑}]$；
• $wh_{x,y}$ 为 $[(x,y)\text{ 未被横着涂白}]$；
• $ws_{x,y}$ 为 $[(x,y)\text{ 被横着涂白}]$；

现在来考虑代价，对于横竖涂色，考虑把 $Ak$ 算在每个格子上，把 $B$ 算在末尾格子上。那么有贡献：

• $A\times bh_{x,y}$，$B\times bh_{x,y}(1-bh_{x,y+1})$；
• $A\times bs_{x,y}$，$B\times bs_{x,y}(1-bs_{x+1,y})$；
• $A\times wh_{x,y}$，$B\times wh_{x,y}(1-wh_{x,y+1})$；
• $A\times ws_{x,y}$，$B\times ws_{x,y}(1-ws_{x+1,y})$；

注意边界情况要特判。

然后考虑单点涂色的代价和不合法的情况，显然一个格子不会被以一个方向涂色两次，所以横竖涂色时一个格子的涂色次数不会超过 $2$ 次，不会不合法：

• 最后要涂白的格子 $(x,y)$：
  • 有贡献情况为该格被涂黑了，但未被涂白：$C\times wh_{x,y}(1-bs_{x,y})+C\times bh_{x,y}(1-ws_{x,y})$；
  • 不合法情况为该格已被两次涂黑：$\infin\times bh_{x,y}(1-bs_{x,y})$；
• 最后要涂黑的格子 $(x,y)$：
  • 由于涂白后不能再涂黑，所以有贡献的情况为该格未被涂黑：$C\times (1-bh_{x,y})+C\times bs_{x,y}$；
  • 不合法情况为该格已被涂白：$\infin\times (1-bh_{x,y})+\infin \times bs_{x,y}$；

那么建图跑最小割即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int MS=45,S=10000,BS=100005;

int n,m,A,B,C;
char a[MS][MS];
int s,t;
int esum,to[BS],c[BS],nxt[BS],h[S];
int dep[S];

inline void init()
{
	esum=1;
	memset(h,0,sizeof(h));
	s=0,t=n*m*4+1;
}

inline void add(int x,int y,int w)
{
	to[++esum]=y;
	c[esum]=w;
	nxt[esum]=h[x];
	h[x]=esum;
}

inline void Add(int x,int y,int w)
{
	// printf("%d %d %d\n",x,y,w);
	add(x,y,w);
	add(y,x,0);
}

inline bool bfs()
{
	memset(dep+s,0,(t-s+1)*sizeof(int));
	dep[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i];
			if(c[i]>0&&dep[v]==0)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t]!=0;
}

int dfs(int u,int w)
{
	if(u==t) return w;
	int sum=0;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(c[i]>0&&dep[v]==dep[u]+1)
		{
			int re=dfs(v,min(w,c[i]));
			c[i]-=re;
			c[i^1]+=re;
			w-=re;
			sum+=re;
			if(w==0) break;
		}
	}
	if(sum==0) dep[u]=0;
	return sum;
}

inline int dinic()
{
	int ans=0;
	while(bfs()) ans+=dfs(s,1e8);
	return ans;
}

inline int getid(int x,int y,int id)
{
	return (id-1)*n*m+(x-1)*m+y;
}

inline void slove()
{
	scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);
	for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
	init();
	// 1: 横着涂黑
	// 2: 1-竖着涂黑
	// 3: 1-横着涂白
	// 4: 竖着涂白
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			Add(s,getid(i,j,1),0);
			Add(s,getid(i,j,2),A+(i==n)*B);
			Add(s,getid(i,j,3),A+(j==m)*B);
			Add(s,getid(i,j,4),0);
			Add(getid(i,j,1),t,A+(j==m)*B);
			Add(getid(i,j,2),t,0);
			Add(getid(i,j,3),t,0);
			Add(getid(i,j,4),t,A+(i==n)*B);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m-1;j++)
		{
			Add(getid(i,j,1),getid(i,j+1,1),B);
			Add(getid(i,j+1,3),getid(i,j,3),B);
		}
	}
	for(int i=1;i<=n-1;i++)
	{
		for(int j=1;j<=m;j++)
		{
			Add(getid(i+1,j,2),getid(i,j,2),B);
			Add(getid(i,j,4),getid(i+1,j,4),B);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='#')
			{
				Add(getid(i,j,2),getid(i,j,1),C);
				Add(s,getid(i,j,3),1e8);
				Add(getid(i,j,4),t,1e8);
			}
			else
			{
				Add(getid(i,j,1),getid(i,j,4),C);
				Add(getid(i,j,3),getid(i,j,2),C);
				Add(getid(i,j,1),getid(i,j,2),1e8);
			}
		}
	}
	printf("%d\n",dinic());
}

int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}