Description
秋天到了，有個叫John的農民準備豐收了。由于拖拉機頻繁地上山下山，他去年豐收的開支超出了他的預期。
豐收的時候，他的 n+m 台拖拉機需要橫向把土地掃一遍，再縱向把土地掃一遍。在下面這幅圖中，你可以看到嫩綠色的部分是海拔低的地方，而深綠色的部分是海拔高的地方。收獲的時候，他的拖拉機需要上山和下山，上山和下山的位置用紅色線标出，這些拖拉機一共要上山或下山8次。
這一年，他準備把一些海拔高的土地鏟平變成海拔低的，把一些海拔低的土地填充變成海拔高的來減少拖拉機上山和下山的次數。為了最小化花費，你能幫他決定一下如何鏟平/填充使得花費最小嗎？
John知道拖拉機每次上山或者下山需要花費 a 金币，而把一塊海拔高的土地變成海拔低的土地或者把一塊海拔低的土地變成海拔高的土地需要花費 b 金币。
Input
第一行包含四個整數 n,m,a,b ， n,m 表示農場是一個 n×m 的網格 。
接下來N行，每行M個字元表示John的農場。 '.' 表示海拔低的土地， '#' 表示海拔高的土地。
Output
輸出一個整數表示最少花費。
Sample Input
5 4 1000 2000
…#
#..#
…#
##..
###.
Sample Output
11000
Hint
【樣例解釋】
John有一個5*4的土地，上山下山費用為1000，改變高度費用為2000。
最少花費是11000：将第二行第一個 '#' 改為 '.' ，花費2000，另外上山下山費用為9000。
而不改變任何高度需要花費12000，把所有高土地變低土地需花費18000，把所有低土地變高土地需花費22000。
【資料範圍與約定】
對于25%的資料， n,m≤5
有10%的資料滿足 n=1 或者 m=1
對于所有資料， 1≤n,m≤50,1≤a,b≤105
題解：最小割
将圖放到一個最小割圖裡面
建立源點 S，彙點T，設更改土地費用為cutcost，登上高地的費用為climbcost。
将S向所有低地連一條容量為cutcost的邊，所有高地向T連一條容量為cutcost的邊。
接下來所有點向相鄰點連一條容量為climbcost的邊。
對該圖求一遍最大流即可（最大流等于最小割）。
這樣做的原因是将S集合與T集合分開求最小割。因為S連向了所有低地，T連向了所有高地，而将一塊地的高度變化等價于将該地與相鄰的屬于不同集合的地的邊舍棄。
在上圖中，若 cutc(4−>t)<climbc(3−>4)+climbc(2−>4) 則最大流為 cutc(4−>t)
若 cutc(4−>t)>climbc(3−>4)+climbc(2−>4) 則最大流為 climbc(3−>4)+climbc(2−>4)
相同集合的1、2、3之間不會産生流量，因為他們同屬S集合，若斷開的是 cutc(s−>2) （把2變為高地），那麼就必須斷開 climbc(1−>2) （若斷開 climbc(2−>4) 則不符合最小割性質（同時斷開不是最小割））是以求出來的最大流是原圖的最小割。
代碼：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int INF=;
const int Maxn=;
const int Maxe=Maxn*Maxn*;
int map[Maxn][Maxn];
char ch[Maxn];
int n,m,cutc,clic,src,des,ecnt=,ans;
int cap[Maxe],lev[Maxe],cur[Maxe],last[Maxe],before[Maxe],to[Maxe];
const int fx[]={,,,,-};
const int fy[]={,,-,,};
inline void Add(int x,int y,int c)
{
before[++ecnt]=last[x];
last[x]=ecnt;
to[ecnt]=y;
cap[ecnt]=c;
}
inline void Insert(int x,int y,int z)
{
Add(x,y,z);
Add(y,x,);
}
inline bool Bfs()
{
static int que[Maxe],qn;
for(int i=src;i<=des;i++)lev[i]=-,cur[i]=last[i];
que[qn=]=src,lev[src]=;
for(int ql=;ql<=qn;ql++)
{
int u=que[ql],v,e;
for(e=last[u];e,v=to[e];e=before[e])
{
if(cap[e]&&lev[v]==-)
{
que[++qn]=v;
lev[v]=lev[u]+;
if(v==des)return true;
}
}
}
return false;
}
inline int Dinic(int now,int Maxflow)
{
if(now==des)return Maxflow;
int v,delta,res=;
for(int &e=cur[now];e,v=to[e];e=before[e])
{
if(cap[e]&&lev[v]==lev[now]+)
{
delta=Dinic(v,min(Maxflow-res,cap[e]));
if(delta)
{
cap[e]-=delta;
cap[e^]+=delta;
res+=delta;
if(res==Maxflow)return res;
}
}
}
if(res!=Maxflow)lev[now]=-;
return res;
}
inline void Maxflow()
{
while(Bfs())
ans+=Dinic(src,INF);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&clic,&cutc);
src=,des=n*m+;
for(int i=;i<=n;i++)
{
scanf("%s",ch+);
for(int j=;j<=m;j++)
{
if(ch[j]=='.')map[i][j]=;
else map[i][j]=;
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(map[i][j]==)Insert(src,(i-)*m+j,cutc);
else Insert((i-)*m+j,des,cutc);
for(int k=;k<=;k++)
{
int x=i+fx[k],y=j+fy[k];
if(x>=&&x<=n&&y>=&&y<=m)
{
Insert((i-)*m+j,(x-)*m+y,clic);
}
}
}
}
Maxflow();
printf("%d\n",ans);
return ;
}