Drainage Ditches
memory limit: 65536KB time limit: 1000MS
accept: 114 submit: 238
Description
Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network. Note however, that there can be more than one ditch between two intersections.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.
Input
Line 1: Two space-separated integers, N ( 0 <= N <= 100,000 ) and M ( 2 <= M <= 200 ). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream.
Line 2..N+1: Each of N lines contains three integers, Si, Ei, and Ci. Si and Ei ( 1 <= Si, Ei <= M ) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci ( 0 <= Ci <= 10,000,000 ) is the maximum rate at which water will flow through the ditch.
Output
One line with a single integer, the maximum rate at which water may emptied from the pond.
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
Sample Output
50
Hint
最大流问题，是最水的最大流。这题的数据流比较小，所以可以用邻接矩阵表示的Edmonds-Karp算法过，如果数据量大的话，用邻接表表示的Dinic算法效率比较高。此外还有 SAP、Improved SAP、预流推进算法。
AC代码：
（1）Edmonds_Krap
View Code
1 #include<stdio.h> 2 #include<string.h> 3 int c[201][201],pre[201],max; //c残留网络容量，pre记录增广路径上的点的前驱结点 4 int queue[40000]; 5 int bfs(int m) //找增广路径 6 { 7 int front,rear,i,v; 8 front=0; rear=0; 9 queue[rear++]=1; 10 memset(pre,-1,sizeof(pre)); 11 while(front<rear) //当队列不为空 12 { 13 v=queue[front++]; 14 for(i=1;i<=m;i++) 15 if(pre[i]==-1&&c[v][i]>0) //当顶点i未访问且残留网络中边<v,i>大于0，只有残留容量大于0时才存在边 16 { 17 queue[rear++]=i; 18 pre[i]=v; //记录顶点i的前驱结点v 19 if(i==m) //遇到汇点m，即找到了增广路径 20 return 1; 21 } 22 } 23 return 0; //找不到增广路径 24 } 25 void Edmonds_Karp(int m) 26 { 27 int i,minflow; 28 while(bfs(m)) //增广路径存在时 29 { 30 minflow=10000000; 31 i=m; 32 while(i!=1) //求增广路径中的最小边 33 { 34 if(c[pre[i]][i]<minflow) 35 minflow=c[pre[i]][i]; 36 i=pre[i]; 37 } 38 max+=minflow; 39 i=m; 40 while(i!=1) //更新增广路径上的边的流值 41 { 42 c[pre[i]][i]-=minflow; //求正向的残留网络 43 c[i][pre[i]]+=minflow; //求反向的残留网络 44 i=pre[i]; 45 } 46 } 47 } 48 int main() 49 { 50 int n,m,i,s,e,w; 51 while(scanf("%d%d",&n,&m)!=EOF) 52 { 53 memset(c,0,sizeof(c)); 54 max=0; 55 for(i=0;i<n;i++) 56 { 57 scanf("%d%d%d",&s,&e,&w); 58 c[s][e]+=w; //注意：有重边 59 } 60 Edmonds_Karp(m); 61 printf("%d\n",max); 62 } 63 return 0; 64 }
View Code
1 #include<stdio.h> 2 #include<string.h> 3 int n,m,max,c[201][201],queue[40000],level[201]; 4 int min(int a,int b) 5 { 6 return a<b?a:b; 7 } 8 int bfs() //对顶点进行标号，找出层次图 9 { 10 int front,rear,u,v; 11 front=rear=0; 12 memset(level,0,sizeof(level)); 13 queue[rear++]=1; 14 level[1]=1; 15 while(front<rear) 16 { 17 u=queue[front++]; 18 for(v=1;v<=m;v++) 19 { 20 if(!level[v]&&c[u][v]>0) 21 { 22 level[v]=level[u]+1; 23 queue[rear++]=v; 24 } 25 } 26 } 27 return level[m]!=0; //汇点是否在层次图中 28 } 29 int dfs(int u,int cp) //在层次图中寻找增广路径进行增广 30 { 31 int tmp=cp; 32 int v,t; 33 if(u==m) 34 return cp; 35 for(v=1;v<=m&&tmp;v++) 36 if(level[v]==level[u]+1&&c[u][v]>0) 37 { 38 t=dfs(v,min(tmp,c[u][v])); 39 c[u][v]-=t; 40 c[v][u]+=t; 41 tmp-=t; 42 } 43 return cp-tmp; 44 } 45 void Dinic() 46 { 47 max=0; 48 int tmpflow=0; 49 while(bfs()) //汇点不在层次图中，算法终止 50 { 51 max+=dfs(1,1000000); 52 } 53 } 54 int main() 55 { 56 int u,v,w; 57 while(scanf("%d%d",&n,&m)!=EOF) 58 { 59 memset(c,0,sizeof(c)); 60 while(n--) 61 { 62 scanf("%d%d%d",&u,&v,&w); 63 c[u][v]+=w; 64 } 65 Dinic(); 66 printf("%d\n",max); 67 } 68 return 0; 69 }
（3）dinic（邻接链表）
View Code
1 /***************************************************************************** 2 时间复杂度：O(V^2*E) 3 算法思路：利用构造分层网络的算法来寻找最短路径,首先从s点处进行bfs搜索， 4 dis[s] = 0，然后层次数依次增加，如果搜索到t，则结束。dfs进行搜索， 5 逐层搜索，进行d[v] == d[u] + 1判断，任意一条路径即为最短路径。 6 Dinic 算法的另一个优化之处：找一条增广路径同时可以找到多条，类似增广路径树。 7 如果cur顶点的总残余流量不为零，这样我们就不必要从起点再次开始寻找增广路， 8 而是从cur顶点出发直接开始，这样就会减少了重复计算，提高效率。 9 ******************************************************************************/ 10 #include<stdio.h> 11 #include<string.h> 12 #define INF 0x7fffffff 13 #define maxm 205*2 14 #define maxn 205 15 struct Edge 16 { 17 int v,w,next; 18 }e[maxm]; 19 int first[maxn],level[maxn],que[maxn]; 20 int s,t,g; //s 源点，t 汇点 21 int min(int a,int b) 22 { 23 return a<b?a:b; 24 } 25 void AddEdge(int u,int v,int w) 26 { 27 e[g].v=v; 28 e[g].w=w; 29 e[g].next=first[u]; 30 first[u]=g++; 31 } 32 int bfs() //建层次图，存在可行弧即可结束 33 { 34 memset(level,0,sizeof(level)); 35 int front,rear,u,v,i; 36 front=rear=0; 37 que[rear++]=s; 38 level[s]=1; 39 while(front<rear) 40 { 41 u=que[front++]; 42 if(u==t) 43 return 1; 44 for(i=first[u];i!=-1;i=e[i].next) 45 { 46 v=e[i].v; 47 if(!level[v]&&e[i].w) 48 { 49 level[v]=level[u]+1; 50 que[rear++]=v; 51 } 52 } 53 } 54 return 0; 55 } 56 int dfs(int cur,int maxf) //寻找增广路 57 { 58 if(cur==t) 59 return maxf; 60 int f,i; 61 int ret=0; //多条增广路最大流之和 62 for(i=first[cur];i!=-1;i=e[i].next) 63 { 64 int v=e[i].v; 65 if(e[i].w&&level[v]==level[cur]+1) 66 { 67 f=dfs(v,min(maxf-ret,e[i].w)); 68 e[i].w-=f; 69 e[i^1].w+=f; 70 ret+=f; 71 if(maxf==ret) 72 return ret; 73 } 74 } 75 return ret; 76 } 77 int dinic() 78 { 79 int ret=0; 80 while(bfs()){ //判断是否存在可行弧 81 ret+=dfs(s,INF); 82 } 83 return ret; 84 } 85 int main() 86 { 87 int n,m,u,v,w; 88 while(scanf("%d%d",&m,&n)!=EOF) 89 { 90 s=1; t=n; 91 g=0; 92 memset(first,-1,sizeof(first)); 93 while(m--) 94 { 95 scanf("%d%d%d",&u,&v,&w); 96 AddEdge(u,v,w); //正向边 97 AddEdge(v,u,0); //反向边为0 98 } 99 int ans=dinic(); 100 printf("%d\n",ans); 101 } 102 return 0; 103 }
（4）ISAP
View Code
1 #include<stdio.h> 2 #include<string.h> 3 /********************************************************************* 4 ISAP计算的是反向图的层次图，作用与原图的层次图一样。计算反向图的 5 层次图是便于重新给顶点标号，即计算层次图，具体做法：在查找<u,v> 6 的时候，MinDis = min(dis[v])，这样查找玩所有与顶点u相关的边之后， 7 dis[u] = dis[v] + 1，从而得到新的层次图。在刚开始寻找的时候， 8 我们也不需要计算层次图，对所有dis[]都赋值为0即可，对效率没有多大影响。 9 另外ISAP算法的另一个优化在于：如果层次图出现断层，则直接结束。 10 11 时间复杂度：O(V^2*E) 12 **********************************************************************/ 13 #define maxn 210 14 #define maxm 1000010 15 #define INF 0x7fffffff 16 struct Edge 17 { 18 int v,w,next; 19 }e[maxm]; 20 int s,t,n,m,g; //s 源点，t 汇点，n 顶点个数 21 int first[maxn],numh[maxn],h[maxn],curedge[maxn],pre[maxn]; 22 //numh[]:用于GAP优化的统计高度数量数组；h[]：距离标号数组：curedge[]: 23 //当前弧数组；pre[]前驱数组 24 int min(int a,int b) 25 { 26 return a<b?a:b; 27 } 28 void AddEdge(int u,int v,int w) //建边 29 { 30 e[g].v=v; 31 e[g].w=w; 32 e[g].next=first[u]; 33 first[u]=g++; 34 } 35 int ISAP() 36 { 37 int cur_flow,u,tmp,neck,i; 38 int flow_ans=0; //初始化最大流为0 39 memset(h,0,sizeof(h)); 40 memset(numh,0,sizeof(numh)); 41 memset(pre,-1,sizeof(pre)); 42 for(i=1;i<=n;i++) 43 curedge[i]=first[i]; //初始化当前弧为第一条邻接边 44 numh[0]=n; 45 u=s; 46 while(h[s]<n) //当h[s]>=n时，网络中肯定出现了GAP 47 { 48 if(u==t) 49 { 50 cur_flow=INF; 51 for(i=s;i!=t;i=e[curedge[i]].v) 52 { 53 //增广成功，寻找瓶颈边 54 if(cur_flow>e[curedge[i]].w) 55 { 56 neck=i; 57 cur_flow=e[curedge[i]].w; 58 } 59 } 60 for(i=s;i!=t;i=e[curedge[i]].v) 61 { 62 //修改路径上的边容量 63 tmp=curedge[i]; 64 e[tmp].w-=cur_flow; 65 e[tmp^1].w+=cur_flow; 66 } 67 flow_ans+=cur_flow; 68 u=neck; //下次增广从瓶颈边开始 69 } 70 for(i=curedge[u];i!=-1;i=e[i].next) 71 if(e[i].w&&h[u]==h[e[i].v]+1) 72 break; //寻找可行弧 73 if(i!=-1) 74 { 75 curedge[u]=i; 76 pre[e[i].v]=u; 77 u=e[i].v; 78 } 79 else 80 { 81 if(0==--numh[h[u]]) //GAP优化 82 break; 83 curedge[u]=first[u]; 84 for(tmp=n,i=first[u];i!=-1;i=e[i].next) 85 if(e[i].w) 86 tmp=min(tmp,h[e[i].v]); 87 h[u]=tmp+1; 88 numh[h[u]]++; 89 if(u!=s) //重标号并且从当前点前驱重新增广 90 u=pre[u]; 91 } 92 } 93 return flow_ans; 94 } 95 int main() 96 { 97 int u,v,w; 98 while(scanf("%d%d",&m,&n)!=EOF) 99 { 100 s=1; t=n; 101 g=0; 102 memset(first,-1,sizeof(first)); 103 while(m--) 104 { 105 scanf("%d%d%d",&u,&v,&w); 106 AddEdge(u,v,w); //正向边 107 AddEdge(v,u,0); //反向边 108 } 109 int flow_ans=ISAP(); 110 printf("%d\n",flow_ans); 111 } 112 return 0; 113 }