标签：eof div span 不同 nbsp memset printf 网络流 har
链接：http://codeforces.com/gym/101128
题意：给定一个n*m的地，每块有两种高度，可以花费b将某一块高变低或低变高，有n+m辆车，分别从左往右、从上往下走，经过不同高度的地交界处花费为a，求最小花费。
分析：想到网络流，没想到怎么构造。。。实际上就是要把高和低分开，同时存在高变低和低变高，求最小费用，因此相邻连流量为a的边，源点向低地连流量为b的边，高地向汇点连流量为b的边，最后求一下最小割即可。
1 #include 2 #include 3 #include 4 #include 5 #include 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 edges;
17 vectorint> G[maxn];
18 int a[maxn];
19 int p[maxn];
20 void init(int n){
21 for(int i=0;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 queueint> 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){
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){
70 for(int j=0;j){
71 cin>>field[i][j];
72 }
73 }
74 for(int i=0;i){
75 for(int j=0;j){
76 if(i1){
77 add(i*delta+j,(i+1)*delta+j,a);
78 }
79 if(j1){
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 }
GYM 101128 F.Landscaping(网络流)
标签：eof div span 不同 nbsp memset printf 网络流 har
原文地址：http://www.cnblogs.com/7391-KID/p/7630069.html