题目链接：
https://odzkskevi.qnssl.com/3699857ff0a17d77d1099699cdf4da13?v=1490503337
Description
一块n*m的草坪，有两种高度的草，#表示较高的草，.表示较矮的草，现在要从左往右和从上往下用收割机收割，在相同高度的草坪上收割机不耗油，当高度变化时需要耗花费为a的油，还可以花费b改变任一块草坪的高度，问这n+m排收割机扫过这块草坪需要的最小花费
Input
第一行四整数n,m,a,b分别表示草坪行列数和两种花费，之后一个n*m矩阵表示该草坪(1<=n,m<=50,1<=a,b<=1e5)
Output
输出最小花费
Sample Input 
Sample Output
11000
分析：
这道网络流的题目比较抽象，在没有经验的情况下，根本没看出这是一道网络流。
具体做法就是用所有高地与超级源点建立容量为b的边，所有低地和超级汇点建立容量为b的边，相邻的点之间（不管是不是同为高地还是低地）建立容量为a的边。
先来看一种情况
如果b的值大于a，那么从高地往低地的最终流量就为a,如果a>b，那么最终流量就是b。很明显，网络流就相当于给了一种选择，如果高度变化时所需的花费少那么就选择a,如果更改高度花费少就选择b。还有一个问题就是，如果同为高地或者低地，那为什么之间还要建容量为a的边，其实只要当一条流经过某个点时，它已经是决策过了，因为流量的值为正。可以拿全部为低地或者全部为高地思考一下。
同时也给出来自大佬的分析：
把高草坪看做一个集合S，矮草坪看做一个集合E，问题可以的当做是把这n*m个点分成这两个集合所需的最小代价，高草坪变成矮草坪和矮草坪变成高草坪花费代价b，每块草坪和其四周的草坪之间花费代价a表示高度变化的代价（同样高度也要连，因为不知道是否要改变其中某块的高度，而且如果两块草坪最终高度相同那么就会被分在同一个集合中，那么这个代价就不会被统计），即为求这个图的最小割
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define PI acos(-1.0)
#define eps 1e-8
#define pb push_back
#define MII map<int,int>::iterator
#define MLL map<LL,LL>::iterator
#define pii pair<int,int>
#define SI set<int>::iterator
#define SL set<LL>::iterator
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define ls o<<1
#define rs o<<1|1
#define bug printf("bug-------bug-------bug\n")
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 3000;//最大顶点数
const int maxe = 25005;//最大边数
const int inf = 0x3f3f3f3f;
int n, m, a, b, src, dst;//src超级源点，dst超级汇点
int cnt;//邻接表存图时总的边的数目
int head[maxn];//邻接表初始化
int d[maxn], cur[maxn];//d为分层图的层次数，cur为当前弧
bool vis[maxn];//用于建立分层图时标记是否访问过
char mp[55][55];
void init()
{
memset(head, -1, sizeof(head));
cnt = 0;
}
struct Edge
{
int from, to, cap, flow, nxt;
Edge(){}
Edge(int _from, int _to, int _cap, int _flow, int _nxt):from(_from), to(_to), cap(_cap), flow(_flow), nxt(_nxt){}
}edge[maxe];
void AddEdge(int u, int v, int w)
{
edge[cnt] = Edge(u, v, w, 0, head[u]);
head[u] = cnt++;
edge[cnt] = Edge(v, u, 0, 0, head[v]);
head[v] = cnt++;
}
bool BFS()//建立分层图
{
queue<int> q;
memset(vis, false, sizeof(vis));
vis[src] = true;
d[src] = 0;
q.push(src);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].to, c = edge[i].cap;
if(!vis[v] && c > 0)
{
vis[v] = true;
d[v] = d[u] + 1;
q.push(v);
}
}
}
return vis[dst];//是否还有残余网络能到达汇点
}
int Stack[maxn], top;//栈优化
ll Dinic()
{
ll ret = 0;
while(BFS())
{
//for(int i = 0; i <= dst; i++)
//cur[i] = head[i];
memcpy(cur, head, sizeof(head));//当前弧
int u = src, top = 0;//top表示栈顶的弧
while(true)
{
if(u == dst)
{
int flow = inf, loc;
for(int i = 0; i < top; i++)
if(flow > edge[Stack[i]].cap)
{
flow = edge[Stack[i]].cap;
loc = i;//loc表示增广路中容量最小的边编号
}
for(int i = 0; i < top; i++)//可行边减去流量
{
edge[Stack[i]].cap -= flow;
edge[Stack[i]^1].cap += flow;
}
ret += flow;
top = loc;//采用容量最小的边最为栈顶，进行增广
u = edge[Stack[top]].from;
}
for(int i = cur[u]; i != -1; cur[u] = i = edge[i].nxt)//寻找残余网络中的一条边
if(edge[i].cap && (d[u]+1 == d[edge[i].to]))
break;
if(cur[u] != -1)//如果找到一条可行边，把这条边放到栈顶，用它尾部的点当做起始点去寻找残余网络中接下去的一条边
{
Stack[top++] = cur[u];
u = edge[cur[u]].to;
}
else//如果没有找到一条可行的边
{
if(top == 0)//如果栈中已经没有了可行的边，则表示此次增广完成
break;
d[u] = -1;//该点的出边已经无法增广
u = edge[Stack[--top]].from;//采用当前点的的上一个点作为起点去找增广路
}
}
}
return ret;
}
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int main()
{
while(scanf("%d%d%d%d", &n, &m, &a, &b) != EOF)
{
for(int i = 1; i <= n; i++)
scanf("%s", mp[i]+1);
src = 0;dst = n*m+1;//源点和汇点
init();//邻接表初始化
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(mp[i][j] == '#')
AddEdge(src, (i-1)*m+j, b);
else
AddEdge((i-1)*m+j, dst, b);
for(int k = 0; k < 4; k++)
{
int nx = i + dir[k][0];
int ny = j + dir[k][1];
if(nx < 1 || nx > n || ny < 1 || ny > m)
continue;
AddEdge((i-1)*m+j, (nx-1)*m+ny, a);
}
}
printf("%I64d\n", Dinic());
}
return 0;
}