女強(qiáng)人：http://blog.csdn.net/abcjennifer/article/details/5556455

USACO 4.2.1 Ditch 網(wǎng)絡(luò)最大流問(wèn)題算法小結(jié)

通過(guò) USACO 4.2.1 Ditch 學(xué)習(xí)一下最大流算法 。可惜它給的測(cè)試數(shù)據(jù)幾乎沒(méi)有任何殺傷力，后面測(cè)試時(shí)我們采用 DD_engi 寫(xiě)的程序生成的加強(qiáng)版數(shù)據(jù)。

總體上來(lái)說(shuō)，最大流算法分為兩大類(lèi)：增廣路 (Augmenting Path) 和預(yù)流推進(jìn)重標(biāo)號(hào) (Push Relabel) 。也有算法同時(shí)借鑒了兩者的長(zhǎng)處，如 Improved SAP 。本篇主要介紹增廣路類(lèi)算法，思想、復(fù)雜度及實(shí)際運(yùn)行效率比較，并試圖從中選擇一種兼顧代碼復(fù)雜度和運(yùn)行效率的較好方案。以下我們將會(huì)看到，有時(shí)理論分析的時(shí)間復(fù)雜度并不能很好的反映一種算法的實(shí)際效率。

1. Ford - Fulkerson 方法

所有增廣路算法的基礎(chǔ)都是 Ford - Fulkerson 方法。稱(chēng)之為方法而不是算法是因?yàn)?Ford - Fulkerson 只提供了一類(lèi)思想，在此之上的具體操作可有不同的實(shí)現(xiàn)方案。

給定一個(gè)有向網(wǎng)絡(luò) G(V,E) 以及源點(diǎn) s 終點(diǎn) t ，FF 方法描述如下：

Ford-Fulkerson 方法?(G,s,t)
1?將各邊上流量 f 初始化為?0
2?while?存在一條增廣路徑 p
3? ? ?do?沿路徑 p 增廣流量 f
4?return?f

假設(shè)有向網(wǎng)絡(luò) G 中邊 (i,j) 的容量為 c(i,j) ，當(dāng)前流量為 f(i,j) ，則此邊的剩余流量即為 r(i,j) = c(i,j) - f(i,j) ，其反向邊的剩余流量為 r(j,i) = f(i,j) 。有向網(wǎng)中所有剩余流量 r(i,j) > 0 的邊構(gòu)成殘量網(wǎng)絡(luò) G_f?，增廣路徑p即是殘量網(wǎng)絡(luò)中從源點(diǎn) s 到終點(diǎn) t 的路徑。

沿路徑 p 增廣流量 f 的操作基本都是相同的，各算法的區(qū)別就在于尋找增廣路徑 p 的方法不同。例如可以尋找從 s 到 t 的最短路徑，或者流量最大的路徑。

2. Edmonds - Karp 算法

Shortest Augmenting Path (SAP) 是每次尋找最短增廣路的一類(lèi)算法，Edmonds - Karp 算法以及后來(lái)著名的 Dinic 算法都屬于此。SAP 類(lèi)算法可統(tǒng)一描述如下：

Shortest Augmenting Path
1?x <--?0
2?while?在殘量網(wǎng)絡(luò) G_x?中存在增廣路 s ~> t
3? ? ?do?找一條最短的增廣路徑 P
4? ? ? ? delta <-- min{r_ij:(i,j)?屬于 P}
5? ? ? ? 沿 P 增廣 delta 大小的流量
6? ? ? ? 更新殘量網(wǎng)絡(luò) G_x
7?return?x

在無(wú)權(quán)邊的有向圖中尋找最短路，最簡(jiǎn)單的方法就是廣度優(yōu)先搜索 (BFS)，E-K 算法就直接來(lái)源于此。每次用一遍 BFS 尋找從源點(diǎn) s 到終點(diǎn) t 的最短路作為增廣路徑，然后增廣流量 f 并修改殘量網(wǎng)絡(luò)，直到不存在新的增廣路徑。

E-K 算法的時(shí)間復(fù)雜度為 O(VE²)，由于 BFS 要搜索全部小于最短距離的分支路徑之后才能找到終點(diǎn)，因此可以想象頻繁的 BFS 效率是比較低的。實(shí)踐中此算法使用的機(jī)會(huì)較少。

3. Dinic 算法

BFS 尋找終點(diǎn)太慢，而 DFS 又不能保證找到最短路徑。1970年 Dinic 提出一種思想，結(jié)合了 BFS 與 DFS 的優(yōu)勢(shì)，采用構(gòu)造分層網(wǎng)絡(luò)的方法可以較快找到最短增廣路，此算法又稱(chēng)為阻塞流算法 (Blocking Flow Algorithm)。

首先定義分層網(wǎng)絡(luò) AN(f)。在殘量網(wǎng)絡(luò)中從源點(diǎn) s 起始進(jìn)行 BFS，這樣每個(gè)頂點(diǎn)在 BFS 樹(shù)中會(huì)得到一個(gè)距源點(diǎn) s 的距離 d，如 d(s) = 0，直接從 s 出發(fā)可到達(dá)的點(diǎn)距離為 1，下一層距離為2 ... 。稱(chēng)所有具有相同距離的頂點(diǎn)位于同一層，在分層網(wǎng)絡(luò)中，只保留滿(mǎn)足條件 d(i) + 1 = d(j) 的邊，這樣在分層網(wǎng)絡(luò)中的任意路徑就成為到達(dá)此頂點(diǎn)的最短路徑。

Dinic 算法每次用一遍 BFS 構(gòu)建分層網(wǎng)絡(luò) AN(f)，然后在 AN(f) 中一遍 DFS 找到所有到終點(diǎn) t 的路徑增廣；之后重新構(gòu)造 AN(f)，若終點(diǎn) t 不在 AN(f) 中則算法結(jié)束。DFS 部分算法可描述如下：

?1?p <-- s
?2?while?s 的出度 >?0?do
?3? ? ?u <-- p.top
?4? ? ?if?u != t?then
?5? ? ? ? ?if?u 的出度 >?0?then
?6? ? ? ? ? ? ?設(shè)?(u,v)?為 AN(f)?中一條邊
?7? ? ? ? ? ? ?p <-- p, v
?8? ? ? ? ?else
?9? ? ? ? ? ? ?從 p 和 AN(f)?中刪除點(diǎn) u 以及和 u 連接的所有邊
10? ? ?else
11? ? ? ? ?沿 p 增廣
12? ? ? ? ?令 p.top?為從 s 沿 p 可到達(dá)的最后頂點(diǎn)
13?end?while

?實(shí)際代碼中不必真的用一個(gè)圖來(lái)存儲(chǔ)分層網(wǎng)絡(luò)，只需保存每個(gè)頂點(diǎn)的距離標(biāo)號(hào)并在 DFS 時(shí)判斷 dist[i] + 1 = dist[j] 即可。Dinic 的時(shí)間復(fù)雜度為 O(V²E)。由于較少的代碼量和不錯(cuò)的運(yùn)行效率，Dinic 在實(shí)踐中比較常用。具體代碼可參考 DD_engi 網(wǎng)絡(luò)流算法評(píng)測(cè)包中的標(biāo)程，這幾天 dinic 算法的實(shí)現(xiàn)一共看過(guò)和比較過(guò)將近 10 個(gè)版本了，DD 寫(xiě)的那個(gè)在效率上是數(shù)一數(shù)二的，邏輯上也比較清晰。

?4. Improved SAP 算法

?本次介紹的重頭戲。通常的 SAP 類(lèi)算法在尋找增廣路時(shí)總要先進(jìn)行 BFS，BFS 的最壞情況下復(fù)雜度為 O(E)，這樣使得普通 SAP 類(lèi)算法最壞情況下時(shí)間復(fù)雜度達(dá)到了 O(VE²)。為了避免這種情況，Ahuja 和 Orlin 在1987年提出了Improved SAP 算法，它充分利用了距離標(biāo)號(hào)的作用，每次發(fā)現(xiàn)頂點(diǎn)無(wú)出弧時(shí)不是像 Dinic 算法那樣到最后進(jìn)行 BFS，而是就地對(duì)頂點(diǎn)距離重標(biāo)號(hào)，這樣相當(dāng)于在遍歷的同時(shí)順便構(gòu)建了新的分層網(wǎng)絡(luò)，每輪尋找之間不必再插入全圖的 BFS 操作，極大提高了運(yùn)行效率。國(guó)內(nèi)一般把這個(gè)算法稱(chēng)為 SAP...顯然這是不準(zhǔn)確的，畢竟從字面意思上來(lái)看 E-K 和 Dinic 都屬于 SAP，我還是習(xí)慣稱(chēng)為 ISAP 或改進(jìn)的 SAP 算法。

?與 Dinic 算法不同，ISAP 中的距離標(biāo)號(hào)是每個(gè)頂點(diǎn)到達(dá)終點(diǎn) t 的距離。同樣也不需顯式構(gòu)造分層網(wǎng)絡(luò)，只要保存每個(gè)頂點(diǎn)的距離標(biāo)號(hào)即可。程序開(kāi)始時(shí)用一個(gè)反向 BFS 初始化所有頂點(diǎn)的距離標(biāo)號(hào)，之后從源點(diǎn)開(kāi)始，進(jìn)行如下三種操作：(1)當(dāng)前頂點(diǎn) i 為終點(diǎn)時(shí)增廣 (2) 當(dāng)前頂點(diǎn)有滿(mǎn)足 dist[i] = dist[j] + 1 的出弧時(shí)前進(jìn) (3) 當(dāng)前頂點(diǎn)無(wú)滿(mǎn)足條件的出弧時(shí)重標(biāo)號(hào)并回退一步。整個(gè)循環(huán)當(dāng)源點(diǎn) s 的距離標(biāo)號(hào) dist[s] >= n 時(shí)結(jié)束。對(duì) i 點(diǎn)的重標(biāo)號(hào)操作可概括為 dist[i] = 1 + min{dist[j] : (i,j)屬于殘量網(wǎng)絡(luò)G_f}。具體算法描述如下：

algorithm Improved-Shortest-Augmenting-Path
?1?f <--?0
?2?從終點(diǎn) t 開(kāi)始進(jìn)行一遍反向 BFS 求得所有頂點(diǎn)的起始距離標(biāo)號(hào) d(i)
?3?i <-- s
?4?while?d(s)?< n?do
?5? ? ?if?i = t?then? ??// 找到增廣路
?6? ? ? ? ?Augment
?7? ? ? ? ?i <-- s? ? ??// 從源點(diǎn) s 開(kāi)始下次尋找
?8?????if?G_f?包含從 i 出發(fā)的一條允許弧?(i,j)
?9?????????then?Advance(i)
10?????????else?Retreat(i)? ??// 沒(méi)有從 i 出發(fā)的允許弧則回退
11?return f

procedure?Advance(i)
1?設(shè)?(i,j)?為從 i 出發(fā)的一條允許弧
2?pi(j)?<-- i? ??// 保存一條反向路徑，為回退時(shí)準(zhǔn)備
3?i <-- j? ? ? ??// 前進(jìn)一步，使 j 成為當(dāng)前結(jié)點(diǎn)

procedure?Retreat(i)
1?d(i)?<--?1?+ min{d(j):(i,j)屬于殘量網(wǎng)絡(luò)G_f}????// 稱(chēng)為重標(biāo)號(hào)的操作
2?if?i != s
3? ? ?then?i <-- pi(i)? ??// 回退一步

procedure?Augment
1?pi 中記錄為當(dāng)前找到的增廣路 P
2?delta <-- min{r_ij:(i,j)屬于P}
3?沿路徑 P 增廣 delta 的流量
4?更新殘量網(wǎng)絡(luò) G_f

?算法中的允許弧是指在殘量網(wǎng)絡(luò)中滿(mǎn)足 dist[i] = dist[j] + 1 的弧。Retreat 過(guò)程中若從 i 出發(fā)沒(méi)有弧屬于殘量網(wǎng)絡(luò) G_f?則把頂點(diǎn)距離重標(biāo)號(hào)為 n 。

?雖然 ISAP 算法時(shí)間復(fù)雜度與 Dinic 相同都是 O(V²E)，但在實(shí)際表現(xiàn)中要好得多。要提的一點(diǎn)是關(guān)于 ISAP 的一個(gè)所謂 GAP 優(yōu)化。由于從 s 到 t 的一條最短路徑的頂點(diǎn)距離標(biāo)號(hào)單調(diào)遞減，且相鄰頂點(diǎn)標(biāo)號(hào)差嚴(yán)格等于1，因此可以預(yù)見(jiàn)如果在當(dāng)前網(wǎng)絡(luò)中距離標(biāo)號(hào)為 k (0 <= k < n) 的頂點(diǎn)數(shù)為 0，那么可以知道一定不存在一條從 s 到 t 的增廣路徑，此時(shí)可直接跳出主循環(huán)。在我的實(shí)測(cè)中，這個(gè)優(yōu)化是絕對(duì)不能少的，一方面可以提高速度，另外可增強(qiáng) ISAP 算法時(shí)間上的穩(wěn)定性，不然某些情況下 ISAP 會(huì)出奇的費(fèi)時(shí)，而且大大慢于 Dinic 算法。相對(duì)的，初始的一遍 BFS 卻是可有可無(wú)，因?yàn)?ISAP 可在循環(huán)中自動(dòng)建立起分層網(wǎng)絡(luò)。實(shí)測(cè)加不加 BFS 運(yùn)行時(shí)間差只有 5% 左右，代碼量可節(jié)省 15~20 行。

?5. 最大容量路徑算法 (Maximum Capacity Path Algorithm)

?1972年還是那個(gè) E-K 組合提出的另一種最大流算法。每次尋找增廣路徑時(shí)不找最短路徑，而找容量最大的。可以預(yù)見(jiàn)，此方法與 SAP 類(lèi)算法相比可更快逼近最大流，從而降低增廣操作的次數(shù)。實(shí)際算法也很簡(jiǎn)單，只用把前面 E-K 算法的 BFS 部分替換為一個(gè)類(lèi) Dijkstra 算法即可。USACO 4.2 節(jié)的說(shuō)明詳細(xì)介紹了此算法，這里就不詳述了。

?時(shí)間復(fù)雜度方面。BFS 是 O(E)，簡(jiǎn)單 Dijkstra 是 O(V²)，因此效果可想而知。但提到 Dijkstra 就不能不提那個(gè) Heap 優(yōu)化，雖然 USACO 的算法例子中沒(méi)有用 Heap ，我自己還是實(shí)現(xiàn)了一個(gè)加 Heap 的版本，畢竟 STL 的優(yōu)先隊(duì)列太好用了不加白不加啊。效果也是非常明顯的，但比起 Dinic 或 ISAP 仍然存在海量差距，這里就不再詳細(xì)介紹了。

?6. Capacity Scaling Algorithm

?不知道怎么翻比較好，索性就這么放著吧。叫什么的都有，容量縮放算法、容量變尺度算法等，反正就那個(gè)意思。類(lèi)似于二分查找的思想，尋找增廣路時(shí)不必非要局限于尋找最大容量，而是找到一個(gè)可接受的較大值即可，一方面有效降低尋找增廣路時(shí)的復(fù)雜度，另一方面增廣操作次數(shù)也不會(huì)增加太多。時(shí)間復(fù)雜度 O(E²logU) 實(shí)際效率嘛大約稍好于最前面 BFS 的 E-K 算法，稀疏圖時(shí)表現(xiàn)較優(yōu)，但仍然不敵 Dinic 與 ISAP。

?

USACO 4.2.1

Drainage Ditches

Time Limit:1000MS? Memory Limit:65536K
Total Submit:9 Accepted:5

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

?

Source

USACO 93

#include<cstdio> #include<memory> using namespace std;const int maxnode = 1024; const int infinity = 2100000000;struct edge{int ver; // vertexint cap; // capacityint flow; // current flow in this arcedge *next; // next arcedge *rev; // reverse arcedge(){}edge(int Vertex, int Capacity, edge *Next):ver(Vertex), cap(Capacity), flow(0), next(Next), rev((edge*)NULL){}void* operator new(size_t, void *p){return p;} }*Net[maxnode]; int dist[maxnode]= {0}, numbs[maxnode] = {0}, src, des, n;void rev_BFS(){int Q[maxnode], head = 0, tail = 0;for(int i=1; i<=n; ++i){dist[i] = maxnode;numbs[i] = 0;}Q[tail++] = des;dist[des] = 0;numbs[0] = 1;while(head != tail){int v = Q[head++];for(edge *e = Net[v]; e; e = e->next){if(e->rev->cap == 0 || dist[e->ver] < maxnode)continue;dist[e->ver] = dist[v] + 1;++numbs[dist[e->ver]];Q[tail++] = e->ver;}} }int maxflow(){int u, totalflow = 0;edge *CurEdge[maxnode], *revpath[maxnode];for(int i=1; i<=n; ++i)CurEdge[i] = Net[i];u = src;while(dist[src] < n){if(u == des){ // find an augmenting pathint augflow = infinity;for(int i = src; i != des; i = CurEdge[i]->ver)augflow = min(augflow, CurEdge[i]->cap);for(int i = src; i != des; i = CurEdge[i]->ver){CurEdge[i]->cap -= augflow;CurEdge[i]->rev->cap += augflow;CurEdge[i]->flow += augflow;CurEdge[i]->rev->flow -= augflow;}totalflow += augflow;u = src;}edge *e;for(e = CurEdge[u]; e; e = e->next)if(e->cap > 0 && dist[u] == dist[e->ver] + 1)break;if(e){ // find an admissible arc, then AdvanceCurEdge[u] = e;revpath[e->ver] = e->rev;u = e->ver;} else { // no admissible arc, then relabel this vertexif(0 == (--numbs[dist[u]]))break; // GAP cut, Important!CurEdge[u] = Net[u];int mindist = n;for(edge *te = Net[u]; te; te = te->next)if(te->cap > 0)mindist = min(mindist, dist[te->ver]);dist[u] = mindist + 1;++numbs[dist[u]];if(u != src)u = revpath[u]->ver; // Backtrack}}return totalflow; }int main(){int m, u, v, w;freopen("ditch.in", "r", stdin);freopen("ditch.out", "w", stdout);while(scanf("%d%d", &m, &n) != EOF){ // POJ 1273 need this while loopedge *buffer = new edge[2*m];edge *data = buffer;src = 1; des = n;while(m--){scanf("%d%d%d", &u, &v, &w);Net[u] = new((void*) data++) edge(v, w, Net[u]);Net[v] = new((void*) data++) edge(u, 0, Net[v]);Net[u]->rev = Net[v];Net[v]->rev = Net[u];}rev_BFS();printf("%d/n", maxflow());delete [] buffer;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/lgh1992314/archive/2013/06/03/5834989.html

總結(jié)

以上是生活随笔為你收集整理的算法艺术——网络最大流的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。