题意
有一片h*w的草坪，要把每一行从左到右修剪一遍，每一列从上到下修剪一遍。每个草坪要么是高低要么是平地。割草机从高地到平地或者从平地到高地，需要花费a。也可以把平地变为高地或者把高地变为平地，花费为b。求出最小花费是多少。
分析
网络流，应该也不算网络流里的难题，建图还是比较好想的（虽然我不会）。
当时在场上瞎几把建图，最后还是没过
这场结束后问了一下二发学长，恍然大悟。
把草地分为两个集合S和T,平地为S集合，高地位T集合，然后用最少的花费将两个集合分开，那么就是最小割了。
从s（源点）向每个平地连一条容量为b的边，从每个高地向t（汇点）连一条容量为b的边。如果需要把平地变高地或者把高低变平地，就割这几条边就可以了。
每个小草坪都向左边和下面的小草坪连双向边。为什么是双向边？因为是按照每个小草地的性质分为的两大集合。也可以理解为有可能从平地开始，也有可能从高地开始。
然后跑dinic就可以惹~~
下面是代码~
其实没啥看的，建图很简单，dinic是网上的模板··雾
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std; #define N 5000
#define INF 2147483000 struct Edge
{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
}; struct Dinic
{
int n,m,s,t;//结点数，边数（包括反向弧），源点编号，汇点编号
vector<Edge>edges;//边表，dges[e]和dges[e^1]互为反向弧
vector<int>G[N];//邻接表，G[i][j]表示结点i的第j条边在e数组中的编号
bool vis[N]; //BFS的使用
int d[N]; //从起点到i的距离
int cur[N]; //当前弧下标 void addedge(int from,int to,int cap)
{
edges.push_back(Edge(from,to,cap,));
edges.push_back(Edge(to,from,,));
int m=edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
} bool bfs()
{
memset(vis,,sizeof(vis));
queue<int>Q;
Q.push(s);
d[s]=;
vis[s]=;
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=;i<G[x].size();i++)
{
Edge&e=edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)//只考虑残量网络中的弧
{
vis[e.to]=;
d[e.to]=d[x]+;
Q.push(e.to);
}
} }
return vis[t];
} int dfs(int x,int a)//x表示当前结点，a表示目前为止的最小残量
{
if(x==t||a==)return a;//a等于0时及时退出，此时相当于断路了
int flow=,f;
for(int&i=cur[x];i<G[x].size();i++)//从上次考虑的弧开始，注意要使用引用，同时修改cur[x]
{
Edge&e=edges[G[x][i]];//e是一条边
if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>)
{
e.flow+=f;
edges[G[x][i]^].flow-=f;
flow+=f;
a-=f;
if(!a)break;//a等于0及时退出，当a!=0,说明当前节点还存在另一个曾广路分支。 }
}
return flow;
} int Maxflow(int s,int t)//主过程
{
this->s=s,this->t=t;
int flow=;
while(bfs())//不停地用bfs构造分层网络，然后用dfs沿着阻塞流增广
{
memset(cur,,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}
}dinic;
int h,w,a,b;
char G[][];
const int dx[]={,,,-};
const int dy[]={,-,,};
int main(){
scanf("%d%d%d%d",&h,&w,&a,&b);
dinic.s=,dinic.t=h*w+; for(int i=;i<=h;i++){
for(int j=;j<=w;j++){
scanf(" %c",&G[i][j]);
if(G[i][j]=='.')
dinic.addedge(dinic.s,(i-)*w+j,b);
else
dinic.addedge((i-)*w+j,dinic.t,b);
}
}
for(int i=;i<=h;i++){
for(int j=;j<=w;j++){
int u=(i-)*w+j;
int v1=i*w+j;
int v2=(i-)*w+j+;
if(i<h){
dinic.addedge(u,v1,a);dinic.addedge(v1,u,a);
}
if(j<w){
dinic.addedge(u,v2,a);dinic.addedge(v2,u,a);
}
}
}
int ans=dinic.Maxflow(dinic.s,dinic.t);
cout<<ans;
return ;
}