题意：
有一个花园，有些地方是草地，有些地方是洞，现在要在这个花园中修建一个泳池，泳池全部由洞构成。
把洞变成草地需要花费一定的费用，把草地变成洞也需要花费一定的费用，并且泳池的边缘的草地上必须修建防护栏，也需要一定的费用。
花园的边缘地带一定得是草地。
问修建这个泳池的最少花费。
思路：
由于是把洞和草地分开，那么就充当了一个天然的“割”。这个割把草地的点和洞的点分开。
所以从\(S\)向所有除边缘地带的草地连边，容量为对应的费用，表示这个点变成洞需要付出的代价；
从\(S\)向边缘地带的草地和洞连边，容量为inf，表示不可能变成洞，代价为无穷，边缘的洞的费用可以提前计算出来；
从所有的非边缘洞向\(T\)连边，容量为对应的费用，表示把这个点变成草地的代价；
然后相邻的所有点连边，容量为护栏的费用，表示分隔这两个点的代价；
然后求最大流即可，即是最小割，花费的最少费用。
“最小割建图时的边的容量表示割掉这条边需要付出的代价”。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 55;
const int nei[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
struct edge
{
int u,v,cap;
edge(){}
edge(int u,int v,int cap):u(u),v(v),cap(cap){}
};
vector<edge> es;
char s[N][N];
int mp[N][N];
vector<int> G[N*N];
int S,T;
void adde(int u,int v,int cap)
{
es.push_back(edge(u,v,cap));
es.push_back(edge(v,u,0));
int sz = es.size();
G[u].push_back(sz-2);
G[v].push_back(sz-1);
}
int dis[N*N],gap[N*N];
void bfs()
{
memset(dis,inf,sizeof(dis));
memset(gap,0,sizeof(gap));
dis[T] = 0;
gap[0] = 1;
queue<int> q;
q.push(T);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = 0;i < G[u].size();i++)
{
edge &e = es[G[u][i]];
int v = e.v;
if (dis[v] >= inf)
{
dis[v] = dis[u] + 1;
q.push(v);
gap[dis[v]]++;
}
}
}
}
int dfs(int u,int f)
{
if (u == T) return f;
int res = f;
for (int i = 0;i < G[u].size();i++)
{
edge &e = es[G[u][i]];
int v = e.v;
if (dis[u] == dis[v] + 1 && e.cap > 0)
{
int tmp = dfs(v,min(res,e.cap));
if (tmp)
{
res -= tmp;
e.cap -= tmp;
es[G[u][i]^1].cap += tmp;
}
if (!res)
{
return f;
}
}
}
if (!(--gap[dis[u]])) dis[S] = T + 1;
gap[++dis[u]]++;
return f - res;
}
int isap()
{
int ans = 0;
bfs();
while (dis[S] < T + 1) ans += dfs(S,inf);
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n,m;
S = 0;
memset(mp,-1,sizeof(mp));
es.clear();
for (int i = 0;i <= T;i++) G[i].clear();
scanf("%d%d",&m,&n);
T = n * m + 1;
int d,f,b;
scanf("%d%d%d",&d,&f,&b);
int ans = 0;
for (int i = 1;i <= n;i++)
{
scanf("%s",s[i] + 1);
}
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
mp[i][j] = (i-1) * m + j;
if (i == 1 || j == m || i == n || j == 1)
{
if (s[i][j] == '.')
{
adde(S,mp[i][j],inf);
ans += f;
}
else
{
adde(S,mp[i][j],inf);
}
}
else
{
if (s[i][j] == '.')
{
adde(mp[i][j],T,f);
}
else
{
adde(S,mp[i][j],d);
}
}
}
}
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
for (int k = 0;k < 4;k++)
{
int x = i + nei[k][0],y = j + nei[k][1];
int id = mp[x][y];
if (id == -1) continue;
adde(mp[i][j],id,b);
}
}
}
ans += isap();
printf("%d\n",ans);
}
return 0;
}
/*
3
3 3
5 5 1
#.#
#.#
###
5 4
1 8 1
#..##
##.##
#.#.#
#####
2 2
27 11 11
#.
.#
*/