演算法題｜有上下界限制的網路流
作者：超級碼力233
鏈接：https://ac.nowcoder.com/discuss/183935
來源：牛客網
有上下界限制的網路流
前言：網路流網路流網路流！！！
模型
給定一個網路，一個加權的有向圖 ，其中的每條邊都有一個容量上界
。其中的兩點：
只有出度沒有入度，
只有入度沒有出度。求
到
最大可以流過的流量，這是最大流的模型。
- 容量限制：每條邊的流量
- 流量平衡：任意一個點i，
那麼 是
的一個可行流。最大流即滿足容量限制和流量平衡的最大的流。
如果在網路中，每條邊增加一個流量下界 ，這就是有上下界限制的網路流的模型了。
- 容量限制：每條邊的流量
- 流量平衡：任意一個點i，
有上下界限制的網路流一般分為三類：
- 無源匯有上下界可行流
- 有源匯有上下界最大流
- 有源匯有上下界最小流
----------------------------
下面分別闡述其求法。
Pre Knowledge
B(u,v): u->v的流量下界
C(u,v): u->v的流量上界f(u,v): u->v的流量
無源匯上下界可行流
顧名思義，無源匯上下界可行流：沒有源點 ，匯點
。在網路中求可行流或者指出不存在。
對於這個問題，不好處理，但是如果我們去掉流量下界限制 ，那麼就是最大流的模型了，問題就可以解決了。
直接去掉 是不對的。我們規定初始流：每條邊先流過B的流量。但是初始流可能會不滿足流量平衡。即可能存在：
那麼我們加上一個 （附加流）是其滿足流量平衡。
也就是實際的流量
。
此時我們去掉了流量下界限制 ，那麼網路中每條邊的容量上界限也要減去，已經流過了
的流量，即新網路圖中每條邊的流量上界限制為
，下界限制0。
用最大流求解（求解附加流）：
將(1)式移項：
令
原式：
是已知的，
點的流入的下界之和減流出的下界之和。
1、如果
那麼我們發現附加流中流出的需要比流入的多 纔可以達到流量平衡，那麼這些流從哪來呢。建一個源點SS，建一條從SS到
的邊，容量為
。
2、如果
同理，發現附加流中流入的需要比流出的多 纔可以達到流量平衡。建一匯點
，建一條從
到
點邊，容量
，容量也就變成正的了。
建圖完畢。從 到
跑一遍最大流即可。原圖中存在解的條件是：每條從
連出的邊與連向
的邊都需要滿流。
問題：
1、為什麼從 連出的邊與連向
的邊滿流後才存在解，不滿流就不存在解？
設從 連出的邊其中一條指向
，容量
。思考連這條邊是因為
的下界
中流入的（
）大於流出的（
）。因為在網路圖中已經流了下界的流量，所以附加流中i的出邊要增加一些流量，以達到實際網路圖中的流量平衡。這些增加的流量就是從這條邊流來，如果這條邊未滿流，那麼說明i的所有出邊已經無法再流M的流量了，也就是
的所有出邊的流出的最大值，不及入邊的最小值
，因此不存在解。
相反，如果滿流，那麼說明這個點至少是可以達到流量平衡了，且滿足了容量限制，那麼所有的邊都滿流，就是有解了。
對於連向TT的邊，同理。2、還有一個小問題，會不會 到i的邊未滿流，但是另一指向
的邊使
流量平衡了。
但是仔細想一下，這是不可能存在的。最大流從 開始跑，整個圖中的流量都是從
出發的，而對於
出發的指向i的一條邊，它剛好使得
點流量平衡，哪會有多餘的流量流給其他點呢？
無源匯上下界網路流到此求解完成。
有源匯上下界可行流
有源匯上下界可行流相比有源匯上下界可行流，多了源點 和匯點
，求從
到
滿足每條邊的流量都滿足限制，且除
，其他點都滿足流量平衡。因為只有
和
不滿足流量平衡，所以，如果可以使
也滿足流量平衡，那麼就可以直接套用無源匯上下界可行流了。
那麼具體如何操作呢?
源點的性質是隻有流出的沒有流入的，匯點恰好相反，而且對於源點流出的和匯點流入的，這些流量是相等的。所以建一條從 到
的邊容量為INF，那麼流入匯點的流量就會從這條邊流入
。有源匯到無源匯轉換完成，跑一遍從
到
的最大流即可。可行流的流量也就是這條邊的流量。
無源匯上下界可行流到此求解完成。
無源匯上下界可行流沒有例題，因為在下面兩個中都會用到。
有源匯上下界最大流
有源匯上下界最大流與有源匯上下界可行流相比，不只是可行流，而且要最大。依然每條邊滿足容量限制，除源點匯點滿足流量平衡。
首先，前提是必須有可行流，所以先套用有源匯上下界可行流來判斷是否有解。如果沒解就直接輸出，有解繼續往下看。然後，判斷後的殘量網路上跑一遍從S到T的最大流，讓還有自由流的邊多流一些，然後將可行流與這次的最大流相加即可。
為什麼這樣可以求出最大流？
SS連出的所有邊，容量都是流入的下界之和-流出的下界之和，所以當這些邊都滿流時，說明這些點實際流出的流量=流入的下界之和。那麼流入的上界可能並沒有達到。對於連向TT的邊同樣是這樣。所以在殘餘網路上，可能可以繼續流一些的，從S到T的最大流，剛好把這些流量全加上。此時再加上可行流，就是最大流。
這樣做會不會不滿足流量限制了？
在原圖中SS，TT的邊已經滿流了，而且最後的最大流，是不經過這些邊的，無法改動這些邊的。
代碼實現（兩種方法）：
1、判斷可行流，刪除T->S的邊，求S到T的最大流，answer=可行流+最大流。
2、判斷可行流，求S到T的最大流，answer=最大流。仔細一想就明白了，T->S這條邊不可能走，而它的反向邊S->T容量（可行流）是要走的，所以可行流的流量會從S->T增廣到T。
還有一種求解的方法：
在判斷可行流時，增加了一條T->S的邊，B=0,C = INF。如果存在可行流，那麼T->S這條邊的容量就是可行流的流量，假設這個流量為a。所以，每次我們可以給a一個值，如果存在解，那麼說明這個值是可行的，所以二分a，判斷是否可行即可。
於是，無源匯上下界最大流求解完成。
有源匯上下界最小流
這個相比上面就是求最小流了。
同樣，先判斷是否有解。之後求一遍T到S的最大流，用可行李減去最大流。考慮反向邊的增加量是表示正向邊的減少量，所以求出從T到S的最大減少量就是最小流了。
代碼實現：判斷可行流，刪T->S的邊，求一遍T到S的最大流，answer=可行流-最大流。
完結撒花~~~
與作者交流：https://ac.nowcoder.com/discuss/183935
更多演算法和題解：https://ac.nowcoder.com/acm/contest/discuss
推薦閱讀：
