有上下界網(wǎng)絡(luò)流地初步思考

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

2、個自然數(shù)下界，即最小的流量，那么這題應(yīng)該怎么做呢？為了最終能夠解決問題，不妨來看一個簡化版的問題：在一個有上下界的流網(wǎng)絡(luò) G中，不設(shè)源和匯，但要求任意一個點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，或指出這樣的可行流不存在。不妨稱這個問題為 無源匯的可行流。首先很顯然的，我們可以想到，如果把所有邊的下界都一定要取到， 所以把它們 都從上界中減去，然后再在剩下來的網(wǎng)絡(luò)中求一個可行流。 那么它是原來網(wǎng)絡(luò)中 的可行流嗎？這樣的轉(zhuǎn)化是不對的，因

3、為它并不滿足流量守恒這一個條件。為了彌補這一不足，我們可以給這個轉(zhuǎn)化過的網(wǎng)絡(luò)附加上一個源和匯。如果設(shè)：M(i) B(u,i) B(i,v)(u,i) E(i,v) E即M(i)為流入結(jié)點i的下界總和減去流出i的下界總和。如果M (i)是正數(shù)設(shè)一附加源So,則可以令C' (So, i) = M(i)。否則設(shè)一附加匯To,令C' (i, To) = - M(i)。如果所有從源點流出的弧和流入?yún)R點的弧都滿載，那么該網(wǎng)絡(luò)存在一個可行流現(xiàn)在我們回到原問題：我們從匯點到源點添加一條上界為無窮大，下界為a的邊，那么如果這個網(wǎng)絡(luò)中 存在可行流，則原網(wǎng)絡(luò)中滿足上下界的最大流流量 >=a。我

4、們可以二分這個a， 從而問題得到解決。這個方法可以很方便的拓展到費用流的情況?！纠?】：變形一筆畫問題在一個有向圖，判斷能不能一筆畫訪問所有的邊，但有些弧上可以畫多次。我們用容量C(u,v)表示弧(u,v)最多可以重復(fù)畫的次數(shù)。非常直觀的問題，我們只要套用上面的模型建立流網(wǎng)絡(luò)。每條有向邊的下界是1(因為必須要畫)，上界是C(u,v)，由于除了開始點和結(jié)束點，每個點進入次數(shù)與離開次數(shù)是相同的。因此滿足流平衡條件，可以想到用流模型做。但這里每條 弧都要畫到，即最少要畫一次。因此，成為 有上下界的網(wǎng)絡(luò)流問題。0, +x【例4】：鐵拳(jsoi2012第二輪) 給定n個未知數(shù)，以及m條方程，其中未知數(shù)

5、系數(shù)絕對值為 1，保證等式之間 沒有相同的單項。再給出每個未知數(shù)的范圍約束。求每個未知數(shù)的取值范圍。先忽略每個未知數(shù)的范圍約束。假設(shè)每個選手的出道和退役時間都不是 0，那么對于每個未知數(shù)，就恰有一正一 負兩個單項，把每條方程看成一個點，那么一正一負就相當(dāng)于流量平衡， 邊的流 量就相當(dāng)于是這個未知數(shù)的值。假如某個選手的出道時間為0，那代表他的邊就從源點出發(fā)；如果退役時間是0， 那代表他的邊就指向匯點。現(xiàn)在考慮未知數(shù)的范圍約束，實際上就是對代表他的邊加上上下界限制。解決了關(guān)于未知數(shù)的構(gòu)圖，現(xiàn)在再討論方程的構(gòu)圖：方程中除了未知數(shù)，還有一個常數(shù) c。如果c>0 ,那么它向匯點連邊，容量上下 界均

6、為c；否則源點向它連邊，容量上下界均為-c。由此我們成功構(gòu)造出了一個 上下界網(wǎng)絡(luò)流模型，問題有解的充要條件是這個網(wǎng)絡(luò) 流存在可行流現(xiàn)在，我們來思考如何得出答案。由于題目所求范圍不要求同時成立，我們可以對每個選手逐個擊破。對于某位特定的選手，其薪金上限和下限是對稱性問題，以下僅討論上限。假如一個選手的薪金滿足范圍0,t，那么對于0，他的薪金也必然滿足范圍0,t+ 。也就是說這個上限滿足二分性質(zhì)。我們可以二分這個邊界，然后改變代表這位選手的邊的上下界，按照上文方法構(gòu) 圖，求解看是否存在可行流即可?！纠?】志愿者招募（noi2008 ）申奧成功后，布布經(jīng)過不懈努力，終于成為奧組委下屬公司人力資源部門

7、的主管。 布布剛上任就遇到了一個難題：為即將啟動的奧運新項目招募一批短期志愿者。 經(jīng)過估算，這個項目需要N天才能完成，其中第i天至少需要Ai個人。 布布通過了解得知，一共有 M類志愿者可以招募。其中第i類可以從第Si天 工作到第Ti天，招募費用是每人 Ci元。新官上任三把火，為了出色地完成自 己的工作，布布希望用盡量少的費用招募足夠的志愿者，但這并不是他的特長！ 于是布布找到了你，希望你幫他設(shè)計一種最優(yōu)的招募方案。解法1 :這也是能找到的最多一種解法 舉樣例的例子來說明吧一共3天 每天需要的最少志愿者數(shù)量分別是 2 3 4有3類志愿者：第一類 可以從第1天到第2天一個人的費用是2第二類 可以從

8、第2天到第3天一個人的費用是3第三類只有第三天一個人的費用是4假設(shè)第i類志愿者的數(shù)量是xi以上可以列為不等式：x1>=2x1+x2>=3x2+x3>=4要求最小化目標函數(shù) 2*x1+5*x2+2*x3發(fā)現(xiàn)是一個線性規(guī)劃問題首先先轉(zhuǎn)化為標準式（新增變量）x1-y 仁2x1+x2-y2=3x2+x3-y3=4其中所有變量大于等于零目標沒變此時在前面和后面都添加一個式子0=0然后用第i個式子減去第i+1個式子得到n+1個新式子 再把常數(shù)項左移 得：-x1+y1+2=0-y1-x2+y2+1=0x1-y2-x3+y3+仁0x2+x3-y3-4=0所有這些式子左右分別相加可以得到0=0

9、經(jīng)觀察可知每個變量在這些式子里都出現(xiàn)過兩次且一正一負（因為每個志愿者時間是連續(xù)的）又因為每個式子可以看成一個流量守恒的點所以 如果一個式子有一個負系數(shù)的變量那么就相當(dāng)于是流出否則就是流入常數(shù)項可以看做和源點或者匯點的流量然后一遍最小費用最大流解法2 :我們把每一天看做一個點，第i天到第i+1天連一條下界是需要人數(shù)，上界是無 窮大，費用為0的邊對于每種志愿者從結(jié)束天數(shù)+1 ,到開始天數(shù)，連一條下界是0，上界是無窮大， 費用是雇傭價格的邊這樣，對于圖中的每一個環(huán)，都代表是招募了一個志愿者。這個圖的有上下界的 最小費用可行流 就是我們需要的答案。這道題目得到了優(yōu)美的解決?！究偨Y(jié)】可以發(fā)現(xiàn)最小割問題多數(shù)情況下是求解一類最優(yōu)化的問題，