1、實用標準文案一類有上下界網絡流問題的初步思考金陵中學王立力引言：最大流類的模型在當今信息學比賽中有相當廣泛的應用， 本文主要討論一類有上下界的網絡流問題， 通過對最大流模型， 特別是附加網絡的一些分析、 討論，達到拋磚引玉目的。從基本問題說起【例 1】: 下圖表示一個河流網 ,V1 是源頭 ,V6 表示入海口 , 每段河道的通過能力 ( 容量 ) 如圖上的各邊上的數據 , 求單位時間內從入海口出去的流量是多少 ?這是一個基本的最大流問題。 解決這個問題，我們只需要按照題意建立網絡模型，并求一遍最大流即可。常用的最大流算法有dinic算法， sap 算法等。一個拓展的例子【例 2】：上面這一題中

2、每條邊的下界是 0，如果規定了上面這個網絡每條邊的一個自然數下界，即最小的流量，那么這題應該怎么做呢？為了最終能夠解決問題，不妨來看一個簡化版的問題：在一個有上下界的流網絡G中，不設源和匯， 但要求任意一個點i 都滿足流量平衡條件：f (u, i )f (i , v)(u ,i )E( i,v )E精彩文檔實用標準文案且每條邊 ( u, v) 都滿足容量限制B( u, v) f ( u, v) C( u,v) 的條件下，尋找一個可行流 f ，或指出這樣的可行流不存在。不妨稱這個問題為 無源匯的可行流 。首先很顯然的， 我們可以想到， 如果把所有邊的下界都一定要取到， 所以把它們都從上界中減去，

3、 然后再在剩下來的網絡中求一個可行流。 那么它是原來網絡中的可行流嗎？這樣的轉化是不對的，因為它并不滿足流量守恒這一個條件。為了彌補這一不足，我們可以給這個轉化過的網絡附加上一個源和匯。如果設：M (i )B(u, i )B(i , v)(u ,i )E(i,v )E即 M( i ) 為流入結點 i 的下界總和減去流出 i 的下界總和。如果 M( i ) 是正數設一附加源 S0，則可以令 C( S0 , i ) = M( i ) 。否則設一附加匯 T0 ，令C( i ,T0) = -M( i ) 。如果所有從源點流出的弧和流入匯點的弧都滿載，那么該網絡存在一個可行流現在我們回到原問題：我們從匯

4、點到源點添加一條上界為無窮大， 下界為 a 的邊，那么如果這個網絡中存在可行流，則原網絡中滿足上下界的最大流流量 >=a。我們可以二分這個 a，從而問題得到解決。這個方法可以很方便的拓展到費用流的情況。【例 3】：變形一筆畫問題在一個有向圖， 判斷能不能一筆畫訪問所有的邊， 但有些弧上可以畫多次。 我們用容量 C(u,v) 表示弧 (u,v) 最多可以重復畫的次數。精彩文檔實用標準文案非常直觀的問題，我們只要套用上面的模型建立流網絡。每條有向邊的下界是 1 （因為必須要畫），上界是 C(u,v) ，由于除了開始點和結束點，每個點進入次數與離開次數是相同的。 因此滿足流平衡條件， 可以想到

5、用流模型做。 但這里每條弧都要畫到，即最少要畫一次。因此，成為 有上下界的網絡流 問題。1,11,41,1121,1351,140, +【例 4】：鐵拳（ jsoi2012第二輪）給定 n 個未知數，以及 m條方程，其中未知數系數絕對值為1，保證等式之間沒有相同的單項。再給出每個未知數的范圍約束。求每個未知數的取值范圍。先忽略每個未知數的范圍約束。假設每個選手的出道和退役時間都不是 0，那么對于每個未知數，就恰有一正一負兩個單項， 把每條方程看成一個點， 那么一正一負就相當于流量平衡， 邊的流量就相當于是這個未知數的值。假如某個選手的出道時間為 0，那代表他的邊就從源點出發； 如果退役時間是

6、0，那代表他的邊就指向匯點。現在考慮未知數的范圍約束，實際上就是對代表他的邊加上上下界限制。解決了關于未知數的構圖，現在再討論方程的構圖：方程中除了未知數，還有一個常數 c。如果 c>0，那么它向匯點連邊，容量上下界均為 c；否則源點向它連邊，容量上下界均為 -c 。由此我們成功構造出了一個 上下界網絡流 模型，問題有解的充要條件是這個網絡流存在可行流現在，我們來思考如何得出答案。由于題目所求范圍不要求同時成立，我們可以對每個選手逐個擊破。對于某位特定的選手，其薪金上限和下限是對稱性問題，以下僅討論上限。精彩文檔實用標準文案假如一個選手的薪金滿足范圍0,t，那么對于 0，他的薪金也必然滿

7、足范圍0,t+ 。也就是說這個上限滿足二分性質。我們可以二分這個邊界， 然后改變代表這位選手的邊的上下界， 按照上文方法構圖，求解看是否存在可行流即可。【例 5】志愿者招募（ noi2008 ）申奧成功后，布布經過不懈努力，終于成為奧組委下屬公司人力資源部門的主管。布布剛上任就遇到了一個難題：為即將啟動的奧運新項目招募一批短期志愿者。經過估算，這個項目需要N 天才能完成，其中第i天至少需要 Ai 個人。布布通過了解得知，一共有M 類志愿者可以招募。其中第i類可以從第Si 天工作到第 Ti天，招募費用是每人Ci 元。新官上任三把火，為了出色地完成自己的工作，布布希望用盡量少的費用招募足夠的志愿者

8、，但這并不是他的特長！于是布布找到了你，希望你幫他設計一種最優的招募方案。解法 1：這也是能找到的最多一種解法舉樣例的例子來說明吧一共 3 天 每天需要的最少志愿者數量分別是2 3 4有3類志愿者：第一類 可以從第 1 天到第 2 天 一個人的費用是 2 第二類 可以從第 2 天到第 3 天 一個人的費用是 3 第三類 只有第三天 一個人的費用是 4 假設第 i 類志愿者的數量是 xi以上可以列為不等式：x1>=2x1+x2>=3x2+x3>=4要求最小化目標函數2*x1+5*x2+2*x3發現是一個線性規劃問題首先先轉化為標準式 ( 新增變量）x1-y1=2精彩文檔實用標準

9、文案x1+x2-y2=3x2+x3-y3=4其中所有變量大于等于零目標沒變此時在前面和后面都添加一個式子0=0然后用第 i 個式子減去第 i+1 個式子得到 n+1 個新式子再把常數項左移得：-x1+y1+2=0-y1-x2+y2+1=0x1-y2-x3+y3+1=0x2+x3-y3-4=0所有這些式子左右分別相加可以得到0=0經觀察可知每個變量在這些式子里都出現過兩次且一正一負 （因為每個志愿者時間是連續的）又因為每個式子可以看成一個流量守恒的點所以 如果一個式子有一個負系數的變量那么就相當于是流出否則就是流入常數項可以看做和源點或者匯點的流量然后一遍最小費用最大流解法 2：我們把每一天看做一個點， 第 i 天到第 i+1 天連一條下界是需要人數， 上界是無窮大，費用為 0 的邊對于每種志愿者從結束天數 +1，到開始天數，連一條下界是 0，上界是無窮大，費用是雇傭價格的邊這樣，對于圖中的每一個環， 都代表是招募了一個志愿者。 這個圖的 有上下界的最小費用可行流 就是我們需要的答案。這道題目得到了優美的解決。【總結】可以發現最小割問題多數情況下是求解一類最優化的問題， 最大流