【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