【USACO4.2.1】草地排水网络流最大流

2019-11-08 01:47:21

字体：大中小

来源：转载

供稿：网友

题目描述

　　在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。　　农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。　　根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

题目大意

有向图最大流

数据范围

N,M≤200

样例输入

5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10

样例输出

解题思路

算法思想：利用距离标号，寻找允许路来得到最短增广路。在找不到允许弧时让距离标号增加。算法步骤：　　(1)dis(s)=0，因为离自已的距离为0。　　(2)对残量网络N(x)的任意一条弧(i,j)，dis(i)<=dis(j)+1，即距离标号不能太大。　　(3)如果残量网络N(x)中的弧满足dis(i)=dis(j)+1(且map[i][j] > 0)，我们称(i,j)是允许弧。只由允许弧组成的路是允许路。显然，允许路是残量网络N(x)中的最短增广路，但是最短增广路并不一定对应一条允许路，因此有时候需要修改距离标号dis[i] = min{ dis[j] + 1 | map[i][j] > 0);通过增加一些弧来得到允许路。如此容易知道当dis[s] = n时就增广完毕，因为从源点到汇点最多有n-1步。最初dis数组可以用一个BFS初始化，但是实践中dis全部初始为0。

代码

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>using namespace std;inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int n,m,cnt=0,h[205],dis[205],gap[205];struct node{int to,next,v,pair;}e[405];void AddEdge2(int x,int y,int v,int pa){e[cnt].to=y;e[cnt].next=h[x];e[cnt].v=v;e[cnt].pair=pa;h[x]=cnt;}//用邻接表的小优化void AddEdge(int x,int y,int v){ AddEdge2(x,y,v,++cnt+1);//正向边 AddEdge2(y,x,0,++cnt-1);//反向边}int SAP(int x,int Maxflow){ if(x==n)return Maxflow;//如果到了终点则返回Maxflow int tmp=Maxflow; for(int p=h[x];p;p=e[p].next){ int y=e[p].to;//枚举可到达的顶点 int flow=min(e[p].v,tmp);//这条边能流过的量为边与当前剩余流量的最小值 if(flow&&(dis[x]==dis[y]+1)){//如果有流量并且编号相邻 int ret=SAP(y,flow); tmp-=ret;//剩余流量减去用过的流量 e[p].v-=ret;//边剩余流量减去流量 e[e[p].pair].v+=ret;//反向边加上流量（应该是叫后悔操作吧） if(dis[1]==n||!tmp)return Maxflow-tmp;//如果起点的标号已经到了N或者当前点已经没有流量了则返回 } } if(!(--gap[dis[x]]))dis[1]=n;//断层了，故将dis[1]设为n，直接终止main中的while else gap[++dis[x]]++;//当前标号加一，gap标号也加一 return Maxflow-tmp;}int main(){ memset(dis,0,sizeof(dis)); int Ans=0; m=Getint(),n=Getint(); for(int i=1;i<=m;i++){ int x=Getint(),y=Getint(),v=Getint(); AddEdge(x,y,v);//建边 } gap[0]=n;//初始标号均为0 while(dis[1]<n)Ans+=SAP(1,1<<30);//SAP求最大流 cout<<Ans; return 0;}

上一篇：二、ListView - model数据绑定

下一篇：buddy system