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

以上就是關於這道題的題解了，關鍵是在建圖上，套路很巧妙，把費用看成了流，值得動手敲一敲。