• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            最大流問題

            最近又復(fù)習(xí)了下最大流問題,每次看這部分的內(nèi)容都會有新的收獲??梢哉f最大流問題的資料網(wǎng)上一搜一大把,根本沒有必要自己寫;但是大部分資料上的專業(yè)術(shù)語太多了,初學(xué)很難理解,至少我當(dāng)年學(xué)這部分的時候前幾次就沒有看懂。所以我準(zhǔn)備備份一點個人的理解。

            圖-1

             

             

              如圖-1所示,在這個運輸網(wǎng)絡(luò)中,源點S和匯點T分別是1,7,各邊的容量為C(u,v)。圖中紅色虛線所示就是一個可行流。標(biāo)準(zhǔn)圖示法如圖-2所示:


             

             

            其中p(u,v) / c(u,v)分別表示該邊的實際流量與最大容量。

             

            關(guān)于最大流

              熟悉了什么是網(wǎng)絡(luò)流,最大流也就很好理解了。就是對于任意的uV-{s},使得p(s,u)的和達到最大。上面的運輸網(wǎng)絡(luò)中,最大流如圖-3所示:MaxFlow=p(1,2)+p(1,3)=2+1=3

              在介紹最大流問題之前,先介紹幾個概念:殘余網(wǎng)絡(luò),增廣路徑,反向弧,最大流定理以及求最大流的Ford-Fulkerson方法。

            殘余網(wǎng)絡(luò) 增廣路徑 反向弧

              觀察下圖-4,這種狀態(tài)下它的殘余網(wǎng)絡(luò)如圖-5所示:



               

             

              也許現(xiàn)在你已經(jīng)知道什么是殘余網(wǎng)絡(luò)了,對于已經(jīng)找到一條從S T的路徑的網(wǎng)絡(luò)中,只要在這條路徑上,把C(u,v)的值更新為C(u,v)-P(u,v),并且添加反向弧C(v,u)。對應(yīng)的增廣路徑Path為殘留網(wǎng)絡(luò)上從ST的一條簡單路徑。圖-41,2,4,7就是一條增廣路徑,當(dāng)然還有1347

              此外在未做任何操作之前,原始的有向圖也是一個殘余網(wǎng)絡(luò),它僅僅是未做任何更新而已。

             

            最大流定理

              如果殘留網(wǎng)絡(luò)上找不到增廣路徑,則當(dāng)前流為最大流;反之,如果當(dāng)前流不為最大流,則一定有增廣路徑。

             

            Ford-Fulkerson方法

              介紹完上面的概念之后,便可以用Ford-Fulkerson方法求最大流了。為什么叫Ford-Fulkerson方法而不是算法,原因在于可以用多種方式實現(xiàn)這一方法,方式并不唯一。下面介紹一種基于廣度優(yōu)先搜索(BFS)來計算增廣路徑P的算法:Edmonds-Karp算法。

              算法流程如下:

              設(shè)隊列Q:存儲當(dāng)前未訪問的節(jié)點,隊首節(jié)點出隊后,成為已檢查的標(biāo)點;

              Path數(shù)組:存儲當(dāng)前已訪問過的節(jié)點的增廣路徑;

              Flow數(shù)組:存儲一次BFS遍歷之后流的可改進量;

              Repeat:

                Path清空;

                源點S進入PathQPath[S]<-0,Flow[S]<-+∞;

                While Q非空 and 匯點T未訪問 do

                    Begin

                        隊首頂點u出對;

                        For每一條從u出發(fā)的弧(u,v) do

                            If v未訪問 and (u,v) 的流量可改進;

                            Then Flow[v]<-min(Flow[u],c[u][v]) and v入隊 and Path[v]<-u

                End while

               

                If(匯點T已訪問)

                Then 從匯點T沿著Path構(gòu)造殘余網(wǎng)絡(luò);

              Until 匯點T未被訪問

             

            應(yīng)用實例

              這是一道最大流的入門題,題目如下:

              http://acm.pku.edu.cn/JudgeOnline/problem?id=1273

            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.
            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

              The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) 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. Each of the following 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

              For each case, output 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

             1 #include <iostream>
             2 #include <queue>
             3 using namespace std;
             4 
             5 const int N = 210;
             6 const int INF = 0x7FFFFFFF;
             7 int n,m,map[N][N],path[N],flow[N],start,end;
             8 queue<int> q;
             9 
            10 int bfs(){
            11     int i,t;
            12     while(!q.empty()) q.pop();
            13     memset(path,-1,sizeof(path));
            14     path[start]=0,flow[start]=INF;
            15     q.push(start);
            16     while(!q.empty()){
            17         t=q.front();
            18         q.pop();
            19         if(t==end) break;
            20         for(i=1;i<=m;i++){
            21             if(i!=start && path[i]==-1 && map[t][i]){
            22                 flow[i]=flow[t]<map[t][i]?flow[t]:map[t][i];
            23                 q.push(i);
            24                 path[i]=t;
            25             }
            26         }
            27     }
            28     if(path[end]==-1return -1;
            29     return flow[m];                   //一次遍歷之后的流量增量
            30 }
            31 int Edmonds_Karp(){
            32     int max_flow=0,step,now,pre;
            33     while((step=bfs())!=-1){          //找不到增路徑時退出
            34         max_flow+=step;
            35         now=end;
            36         while(now!=start){
            37             pre=path[now];
            38             map[pre][now]-=step;      //更新正向邊的實際容量
            39             map[now][pre]+=step;      //添加反向邊
            40             now=pre;
            41         }
            42     }
            43     return max_flow;
            44 }
            45 int main(){
            46     int i,u,v,cost;
            47     while(scanf("%d %d",&n,&m)!=EOF){
            48         memset(map,0,sizeof(map));
            49         for(i=0;i<n;i++){
            50             scanf("%d %d %d",&u,&v,&cost);
            51             map[u][v]+=cost;           //not just only one input
            52         }
            53         start=1,end=m;
            54         printf("%d\n",Edmonds_Karp());
            55     }
            56     return 0;
            57 }
            58 

            posted on 2009-04-19 20:58 極限定律 閱讀(13485) 評論(15)  編輯 收藏 引用 所屬分類: ACM/ICPC

            評論

            # re: 最大流問題[未登錄] 2009-05-29 10:46 Wing

            嗯, 您的一些文章很有獨特的見解, 以后定期過來學(xué)習(xí)~ O(∩_∩)O哈哈~
            希望您再接再厲, 順便預(yù)祝 有道難題, 百度之星 獲得好成績  回復(fù)  更多評論   

            # re: 最大流問題 2009-08-03 09:57 Leng

            很好很詳細  回復(fù)  更多評論   

            # re: 最大流問題 2009-08-13 10:11 va

            好東西啊 經(jīng)常搜到大牛的博客  回復(fù)  更多評論   

            # re: 最大流問題 2010-04-04 23:46 lyt9469

            太好了,深入淺出  回復(fù)  更多評論   

            # re: 最大流問題 2010-06-10 17:19 ss

            4~7的反向邊錯了吧?  回復(fù)  更多評論   

            # re: 最大流問題 2010-11-13 10:37 Crazy_Js

            不錯,寫的很好,
            順便問下我在有些書上看到在尋找可增廣路徑時需要同時尋找包含反向邊的可增路徑,但我也很迷惑我感覺這沒必要,我見你上面的描述也沒有搜索含反向邊的增廣路徑,盼指點迷津,謝謝  回復(fù)  更多評論   

            # re: 最大流問題 2010-11-29 15:47 gdut

            比黑書里面講的好,黑書里面我看不懂  回復(fù)  更多評論   

            # re: 最大流問題 2010-12-10 10:29 中國人

            請問一下, 添加反向邊 有什么道理? 雖然我知道程序是正確的,但不知道為什么要添加反向邊.請指教
              回復(fù)  更多評論   

            # re: 最大流問題 2010-12-13 18:41 ACM初學(xué)者

            收藏了,謝謝了,寫的很好  回復(fù)  更多評論   

            # re: 最大流問題 2010-12-16 18:10 RnMss

            這圖……是……NOI2006WC的……***~~~@@@  回復(fù)  更多評論   

            # re: 最大流問題 2011-12-19 00:44 22

            錯的圖  回復(fù)  更多評論   

            # re: 最大流問題 2011-12-30 20:24 bcydsjbr

            1,1吧@ss
              回復(fù)  更多評論   

            # re: 最大流問題[未登錄] 2012-03-03 12:29 bob

            反向邊是為了給算法一個改正以前錯誤的途徑,自己畫畫就知道了  回復(fù)  更多評論   

            # re: 最大流問題 2012-06-24 22:42 ex

            講解很清晰  回復(fù)  更多評論   

            # re: 最大流問題 2013-10-21 16:47 LittleFIsh

            文章很牛逼,不過有一個小小的錯誤,在圖4和圖5中,有一個地方相沖突,就是圖4中的4和7節(jié)點之間的流量,與圖5中c和t節(jié)點的流量不一致。  回復(fù)  更多評論   

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導(dǎo)航

            統(tǒng)計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            色天使久久综合网天天| 国内精品久久久久国产盗摄| 2021国内久久精品| 久久不见久久见免费视频7| 99久久综合狠狠综合久久止| 欧美一区二区精品久久| 伊色综合久久之综合久久| 久久人人妻人人爽人人爽| 国产高潮久久免费观看| 一本色综合网久久| 久久精品国产精品青草app| 久久国产亚洲精品| 国产成人99久久亚洲综合精品| 香蕉aa三级久久毛片| 久久99国产精一区二区三区 | 亚洲精品国产综合久久一线| 久久一日本道色综合久久| 久久久久久亚洲精品不卡| 人妻无码αv中文字幕久久 | 一本一道久久综合狠狠老| 色综合久久综精品| 精品熟女少妇a∨免费久久| 亚洲美日韩Av中文字幕无码久久久妻妇| 久久久久久国产精品无码超碰| 亚洲国产天堂久久综合| 99久久精品国产毛片| 国产一级持黄大片99久久| 亚洲国产另类久久久精品| 久久久久av无码免费网| 天天做夜夜做久久做狠狠| 66精品综合久久久久久久| 精品久久久久久久久中文字幕| 久久午夜羞羞影院免费观看| 久久伊人精品一区二区三区| 亚洲欧美精品一区久久中文字幕 | 亚洲综合日韩久久成人AV| 色播久久人人爽人人爽人人片AV| 色8激情欧美成人久久综合电| 久久久久无码精品| 久久笫一福利免费导航 | 久久精品国产99国产电影网 |