UVA 1515 Pool construction (网络流dinic)

• 2019 年 11 月 14 日
• 筆記

You are working for the International Company for Pool Construction, a construction company which specializes in building swimming pools. A new client wants to build several new pool areas. A pool area is a rectangular grid of w × h square patches, consisting of zero or more (possibly disconnected) pools. A pool consists of one or multiple connected hole patches, which will later be filled with water. In the beginning, you start with a piece of land where each patch is either a hole in the ground (’.’) or flat grass (’#’). In order to transform this land into a pool area, you must adhere to the following:

• You can leave a patch as it is. This costs nothing.

• If the patch is grass in the beginning, you can dig a hole there. This costs d EUR.

• If the patch is a hole in the beginning, you can fill the hole and put grass on top. This costs f EUR.

• You must place special boundary elements along each edge running between a final grass patch and a final hole patch, to ensure that water does not leak from the pool. This costs b EUR per boundary element.

• The outermost rows and columns of the pool area must always be grass.

You are given the task of calculating the cost of the cheapest possible pool area given the layout of the existing piece of land.

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test case:

• one line with two integers w and h (2 ≤ w, h ≤ 50): the width and height of the building site.

• one line with three integers d, f and b (1 ≤ d, f, b ≤ 10000): the costs for digging a new hole, filling an existing hole, and building a boundary element between a pool and grass patch.

• h lines of w characters each, denoting the layout of the original building site.

Output

Per test case:

• one line with an integer: the cost of building the cheapest possible pool area from the original piece of land.

Sample Input

3

3 3

5 5 1

#.#

#.#

###

5 4

1 8 1

#..##

##.##

#.#.#

#####

2 2

27 11 11

#.

.#

Sample Output

9

27

22

需要的前缀知识：网络流思想和dinic算法。

题意&翻译：给你一个矩形，有些格子是草地，'#'代表草地。有些格子是洞‘. ’，洞可以变成草地，但是需要花费f，草地可以变成洞需要花费d，两个格子之间可以建一个篱笆，花费b。要求是用篱笆围起一个洞（可以多个格子）的最小花费。

这道题一看简直是有毒。好像不知道要怎么做，就算用网络流也不知道如何搞，不知道怎么建边。

那么神奇的地方来了。

首先，我们把边缘的草地连接到源点权值就为INF，边缘的洞变成草地（花费要先累加），连接到源点，流量也为INF(题目说边缘都是草地)。把其他的草地连接到源点，但流量为d，改造为洞的花费，把洞连接到汇点，流量为f改造为草地的花费，任意两个格子之间有一条无向边，流量为b。这就是我们这道题的建图了。看起来很复杂，可能你们也看不出要怎么流。

我们可以把这个地，看成三层。

图中S表示源点，T表示汇点，图中黑色的线是连向所有的草的，画多了怕太花就只花了上下两边。

红色的洞表示这个洞必须得被变成草，所以最后它是连接源点的。现在我们对绿色的洞来分析。如果这个洞没有变成草地，那就得通过3b的流量(篱笆的花费)，如果变成草地就有d+b。现在的问题就是比较这两个流量的大小如果3b>d+b那么就不变成草地，反之成立。

我们把上面的图想象成三层，想一个漏斗，无限的水从边缘通过，经过不同的管道，流到T。值得注意的是我们的水可以从中间的草通过，而不是边缘的草通过，这就表示把草变成了洞，再流向其他地方。能不能这样子搞的前提是我们改洞还是不改洞的方案哪个好。

接下来讲下，围篱笆。其实这是一个割的动作，所有的水流（费用)都会通过篱笆。假设我们草和洞都不变（前提是边缘都是草）那么我们的最终流量是流过所有的草和洞之间的，也就是b*草洞相临的个数。如果我们改变一下，把草改成洞，那么我们就可以直接从源点流向这个草改洞，再流到周围的草洞相临了。这是一个找最小割的过程。那通过最大流最小割定理。我们可以套一下dinic算法。最终可以求得最小费用。

#include<bits/stdc++.h>    using namespace std;  const int maxn=3005;  struct edge  {  	int u,v,cap,flow;  	edge(int a,int b,int c,int f):u(a),v(b),cap(c),flow(f){  	}  };  vector<edge> edges;  vector<int> G[maxn];  int f[maxn];  int p[maxn];int vis[maxn];void add_edge(int u,int v,int cap)  {  	edges.push_back(edge(u,v,cap,0));  	edges.push_back(edge(v,u,0,0));  	int m=edges.size();  	G[u].push_back(m-2);  	G[v].push_back(m-1);  }bool bfs(int s,int t)//dinic算法的分层，算是模板了  {  	queue<int> q;  	q.push(s);  	memset(vis,0,sizeof vis);  	vis[s]=1;  	memset(f,-1,sizeof f);  	f[s]=0;  	while(!q.empty())  	{  		int u=q.front();q.pop();  		for(int i=0;i<G[u].size();i++){  			edge &e=edges[G[u][i]];  			if(!vis[e.v]&&e.cap>e.flow){  				vis[e.v]=1;  				f[e.v]=f[u]+1;  				q.push(e.v);  			}  		}  	}  	return vis[t];  }    int dfs(int s,int t,int flow)//找增广路，也是模板  {  	if(s==t||flow==0)return flow;    	int tt=0;  	int ans=0;  	for(int i=0;i<G[s].size();i++){  		edge &e=edges[G[s][i]];  		if(f[e.v]==f[s]+1&&(tt=dfs(e.v,t,min(e.cap-e.flow,flow)))>0)  		{  			e.flow+=tt;  			edges[G[s][i]^1].flow-=tt;  			ans+=tt;  			flow-=tt;  			if(flow==0)break;  		}  	}  	if(ans==0)return f[s]=-1;  	else  	return ans;  }    int dinic(int s,int t)  {    	int ans=0;  	while(bfs(s,t))  	{  	int val=dfs(s,t,0x3f3f3f3f);  	if(!val)break;  	ans+=val;  	}  	return ans;    }    void init(int n)  {  	for(int i=0;i<=n;i++)G[i].clear();  	edges.clear();  }//以上是dinic的模板，重点在下边  int S,T;  int m,n,d,ff,b;  int id[maxn][maxn];  char g[maxn][maxn];  const int INF=0x3f3f3f3f;    void changnum()//给每个格编一个号，可以说是把二维的格子放到一维  {  	S=0;  	T=m*n+1;  	for(int i=0;i<n;i++){  		for(int j=0;j<m;j++){  			id[i][j]=i*m+j+1;  		}  	}  }  int dx[4] = {0,0,1,-1};  int dy[4] = {-1,1,0,0};  int main()  {  	int t;  	scanf("%d",&t);  	for(int tt=1;tt<=t;tt++)  	{  		scanf("%d%d%d%d%d",&m,&n,&d,&ff,&b);  		init(m*n+1);  		for(int i=0;i<n;++i){  			scanf("%s",g[i]);  		}  		int ans=0;  		changnum();  		for(int i=0;i<n;i++){  			for(int j=0;j<m;j++)  			{  				if(j==0||j==m-1||i==0||i==n-1){  					if(g[i][j]=='.')ans+=ff;//边缘的洞是必须要改为草地的，所有费用得加起来  					add_edge(S,id[i][j],INF);//边缘的草地是无限流量的  				}else {  					if(g[i][j]=='.')  					add_edge(id[i][j],T,ff);//洞到汇点的流量，也就是洞到草的费用  					else add_edge(S,id[i][j],d);//源点到其他的草地是有d的流量的，草地改为石头的流量  				}  				for(int k=0;k<4;++k){  					int ni=i+dx[k],nj=j+dy[k];  					if(ni<0||ni>=n||nj<0||nj>=m)  					continue;  					add_edge(id[i][j],id[ni][nj],b);//每个格子之间建边，流量为b。  				}  			}  		}  		printf("%dn",ans+dinic(S,T));//  	}  }

以上就是关于这道题的题解了，关键是在建图上，套路很巧妙，把费用看成了流，值得动手敲一敲。