链接：http://codeforces.com/gym/101128
题意：给定一个n*m的地，每块有两种高度，可以花费b将某一块高变低或低变高，有n+m辆车，分别从左往右、从上往下走，经过不同高度的地交界处花费为a，求最小花费。
分析：想到网络流，没想到怎么构造。。。实际上就是要把高和低分开，同时存在高变低和低变高，求最小费用，因此相邻连流量为a的边，源点向低地连流量为b的边，高地向汇点连流量为b的边，最后求一下最小割即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<queue> 6 using namespace std; 7 const int delta=50; 8 const int maxn=2505,inf=1e9+5; 9 char field[55][55]; 10 struct Edge{ 11 int from,to,cap,flow; 12 Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} 13 }; 14 struct EdmodsKarp{ 15 int n; 16 vector<Edge> edges; 17 vector<int> G[maxn]; 18 int a[maxn]; 19 int p[maxn]; 20 void init(int n){ 21 for(int i=0;i<n;i++)G[i].clear(); 22 edges.clear(); 23 this->n=n; 24 } 25 void AddEdge(int from,int to,int cap){ 26 edges.push_back(Edge(from,to,cap,0)); 27 edges.push_back(Edge(to,from,0,0)); 28 G[from].push_back(edges.size()-2); 29 G[to].push_back(edges.size()-1); 30 } 31 int Maxflow(int s,int t){ 32 int flow=0; 33 while(1){ 34 memset(a,0,sizeof(a)); 35 queue<int> Q; 36 Q.push(s); 37 a[s]=inf; 38 while(!Q.empty()){ 39 int x=Q.front();Q.pop(); 40 for(int i=0;i<G[x].size();i++){ 41 Edge &e=edges[G[x][i]]; 42 if(!a[e.to]&&e.cap>e.flow){ 43 p[e.to]=G[x][i]; 44 a[e.to]=min(a[x],e.cap-e.flow); 45 Q.push(e.to); 46 } 47 } 48 if(a[t])break; 49 } 50 if(!a[t])break; 51 for(int u=t;u!=s;u=edges[p[u]].from){ 52 edges[p[u]].flow+=a[t]; 53 edges[p[u]^1].flow-=a[t]; 54 } 55 flow+=a[t]; 56 } 57 return flow; 58 } 59 }ek; 60 void add(int s,int t,int cap){ 61 ek.AddEdge(s,t,cap); 62 ek.AddEdge(t,s,cap); 63 } 64 int main(){ 65 // freopen("e:\\in.txt","r",stdin); 66 int n,m,a,b; 67 scanf("%d%d%d%d",&n,&m,&a,&b); 68 ek.init(m*n+2); 69 for(int i=0;i<n;i++){ 70 for(int j=0;j<m;j++){ 71 cin>>field[i][j]; 72 } 73 } 74 for(int i=0;i<n;i++){ 75 for(int j=0;j<m;j++){ 76 if(i<n-1){ 77 add(i*delta+j,(i+1)*delta+j,a); 78 } 79 if(j<m-1){ 80 add(i*delta+j,i*delta+j+1,a); 81 } 82 if(field[i][j]=='#') 83 ek.AddEdge(i*delta+j,delta*delta+1,b); 84 else 85 ek.AddEdge(delta*delta,i*delta+j,b); 86 } 87 } 88 printf("%d\n",ek.Maxflow(delta*delta,delta*delta+1)); 89 return 0; 90 }