题意：有一个水塘，要求把它用围栏围起来，每个费用为b。其中，(#)代表草，(.)代表洞，把一个草变成洞需要费用d， 把一个洞变成草需要费用f。请输出合法方案中的最小费用。
解法：（不好理解......(‘・ω・’)っ）
【思考】
1.围栏把草和洞分隔开了，也就是“割”。但“割”只是把图中的点分成两部分，而这题的草和洞能有多个连通块。因此可以添加源、汇点，使得所有的草和洞接连起来了。
2.先考虑草和洞不能互相转换，那么只有建围栏这一种“割”的方法。所以可以建图，源点→草（由于无限制，容量为INF），草→洞 和 洞→草（容量为b，而不是INF，理解b为走这条边的最少耗费的费用，因为求的是最小割嘛。*(^-^)*），洞→汇点（容量为INF）。
3.而题目的草和洞可以转换，那么我们一定要理解好边容量的意义——走这条边直到汇点被割的最小花费。（但网上有人说是“最大花费”，可能Ta是在“最大流”算法上的理解？）那么对于草转化为洞或者反过来，它们就不用建草与洞之间的围栏了。那么对于1对草和洞的最小割，我们就需对草转化为洞、草与洞之间建围栏和洞转化为草的费用取最小值，也就是图上的边存最小值，源点→草 和 洞→汇点 的容量便由INF分别变为d和f。
【总结】我们需要建源点和汇点使所有草和洞连通起来，再使草在左边与源点相连，洞在右边与汇点相连。要将一对草和洞隔开，可以建围栏、草化为洞或洞化为草，需要选最小的花费的操作。在图中的体现就是一对草和洞的一整条边（源点→草，草→洞，洞→汇点）割最小的花费的边，各自的边容量就是草化为洞、建围栏和洞化为草的花费，这样就可以使这对草和洞成功“分隔”。
【实现】Dinic跑最大流。根据最小割最大流定理：|f|=f(S,T)=Σ(u∈S,v∈T) f(u,v) = Σ(u∈S,v∈T)c (u,v)=c(S,T) , c(S,T)表示这个 s-t割/集合划分(S,T) 的容量。
另外，1. 由于这题是围住水塘，所以外面一圈的洞必须变成草，便转化一下；而且外围的草是不能变成洞，因此与源点连的边的容量应该是INF。
2. 因为草、洞可能变化或不变化，所以所有点与它相邻的点都要连边。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<queue>
6 using namespace std;
7
8 const int N=55,D=10010,NN=3010,MM=30000,INF=(int)1e9;
9 int n,m,len;
10 int last[NN],d[NN];
11 int dx[2]={0,1},dy[2]={1,0};
12 char s[N][N];
13 struct edge{int x,y,fl,next;}a[MM];
14 queue<int> q;
15
16 int mmin(int x,int y) {return x<y?x:y;}
17 int mabs(int x) {return x>0?x:-x;}
18 void ins(int x,int y,int fl)
19 {
20 a[++len].x=x,a[len].y=y,a[len].fl=fl;
21 a[len].next=last[x],last[x]=len;
22 a[++len].x=y,a[len].y=x,a[len].fl=0;
23 a[len].next=last[y],last[y]=len;
24 }
25 bool bfs(int st,int ed)
26 {
27 while (!q.empty()) q.pop();
28 memset(d,0,sizeof(d));
29 q.push(st); d[st]=1;
30 while (!q.empty())
31 {
32 int x=q.front(); q.pop();
33 for (int i=last[x];i;i=a[i].next)
34 {
35 int y=a[i].y;
36 if (d[y]||!a[i].fl) continue;
37 d[y]=d[x]+1;
38 q.push(y);
39 }
40 }
41 return d[ed];
42 }
43 int dfs(int x,int flow,int ed)
44 {
45 if (x==ed) return flow;
46 int sum=0;
47 for (int i=last[x];i;i=a[i].next)
48 {
49 int y=a[i].y,t,tmp;
50 if (d[y]==d[x]+1 && a[i].fl)
51 {
52 t=mmin(flow-sum,a[i].fl);
53 tmp=dfs(y,t,ed);
54 sum+=tmp;
55 a[i].fl-=tmp,a[i^1].fl+=tmp;
56 if (sum==flow) break;
57 }
58 }
59 if (!sum) d[x]=0;
60 return sum;
61 }
62 int Max_flow(int st,int ed)
63 {
64 int sum=0;
65 while (bfs(st,ed)) sum+=dfs(st,INF,ed);
66 return sum;
67 }
68 int ID(int x,int y) {return (x-1)*m+y;}
69 int main()
70 {
71 int T;
72 scanf("%d",&T);
73 while (T--)
74 {
75 scanf("%d%d",&m,&n);
76 int d,f,b;
77 int ans=0,st=n*m+1,ed=n*m+2;
78 scanf("%d%d%d",&d,&f,&b);
79 for (int i=1;i<=n;i++)
80 {
81 scanf("%s",s[i]+1);
82 if (i==1||i==n)
83 {
84 for (int j=1;j<=m;j++)
85 if (s[i][j]=='.') ans+=f, s[i][j]='#';
86 }
87 else
88 {
89 if (s[i][1]=='.') ans+=f, s[i][1]='#';
90 if (s[i][m]=='.') ans+=f, s[i][m]='#';
91 }
92 }
93 len=1;
94 memset(last,0,sizeof(last));//
95 for (int i=1;i<=n;i++)
96 for (int j=1;j<=m;j++)
97 {
98 int t=ID(i,j);
99 if (s[i][j]=='.') ins(t,ed,f);
100 else if (i==1||i==n||j==1||j==m) ins(st,t,INF);
101 else ins(st,t,d);
102
103 for (int k=0;k<2;k++)
104 {
105 int x=i+dx[k],y=j+dy[k],tt=ID(x,y);
106 if (x>n||y>m) continue;
107 //if (s[i][j]!=s[x][y]) //不能加这句因为s[][]可能变化
108 ins(t,tt,b),ins(tt,t,b);//
109 }
110 }
111 for (int i=1;i<=len;i++)
112 int w=1;
113 ans+=Max_flow(st,ed);
114 printf("%d\n",ans);
115 }
116 return 0;
117 }