——沒有什么是一個BFS或一個DFS解決不了的；如果有，那就兩個一起。
最大流的$EK$算法雖然簡單，但時間復雜度是$O(nm^2)$，在競賽中不太常用。
競賽中常用的$Dinic$算法和$SAP$，其實也不太難。
那么，$Dinic$算法到底是什么呢？
?
多路增廣
$Dinic$算法最核心的內容就是多路增廣。
沿著$EK$算法的過程：
我們有一個圖，如圖一。
按照套路，我們先$BFS$，找$S-T$最短路。所有的距離標號都畫在了圖二上（$EK$算法可能用不到，但$Dinic$用得到）。
假設我們選的是$S-3-T$這條路，增廣。。。（如圖三，綠色）
然后我們再來一遍$BFS$。。。 等等！
細心的你可能也發現了，$S-1-T$也是一條$S-T$最短路。
那就增廣吧！（如圖四）
您可以檢查一下，這時候沒有長度為$2$的最短路了。
但EK算法不會這樣。它會再笨拙地$BFS$一遍，這就浪費了不少時間。
所以說，多路增廣是很重要的。
?
我們換一種思路，如果網絡流在一個$DAG$上，還不用考慮回退邊，你會怎么做？
這很簡單，$dfs$就能解決。
至于回退邊。。。再來一次$BFS-DFS$就好了啊。
還有一個優化：當前弧優化：
對于每個點，我可能在一次$BFS$之后$DFS$多次。那么它出發的邊所到的點里， 有些點出發已經滿流。
這樣， 我就可以每個點記錄一個當前弧， 表示這次$DFS$它最后$DFS$到哪條弧，下次$DFS$它的時候就從這條弧開始。
這樣，我就可以保證每條邊在一次$DFS$中滿流后不會再遍歷。
這樣的復雜度。。。理論上最壞是$O(n^2m)$，但這上界很松。
附代碼！
1 int n; 2 3 struct Dinic{ 4 struct Edge{ 5 int from, to; 6 LL cap, flow; 7 Edge(int f = -1, int t = -1, LL c = 0) 8 :from(f), to(t), cap(c), flow(0) 9 {} 10 }edges[MAXM]; 11 int next[MAXM], cnt; 12 int pre[MAXN], dis[MAXN]; 13 int cur[MAXN]; //當前弧 14 Dinic() 15 { 16 memset(pre, -1, sizeof(pre)); 17 cnt = 0; 18 } 19 void addedge(int f, int t, LL c) 20 { 21 edges[cnt] = Edge(f, t, c); 22 next[cnt] = pre[f]; 23 pre[f] = cnt++; 24 edges[cnt] = Edge(t, f, 0); 25 next[cnt] = pre[t]; 26 pre[t] = cnt++; 27 } 28 queue<int> Q; 29 bool BFS(int s, int t) 30 { 31 while(!Q.empty()) Q.pop(); 32 memset(dis, -1, sizeof(dis)); 33 dis[s] = 0; 34 Q.push(s); 35 while(!Q.empty()) 36 { 37 int u = Q.front(); Q.pop(); 38 for(int i = pre[u]; i >= 0; i = next[i]) if(edges[i].cap > edges[i].flow) 39 { 40 int v = edges[i].to; 41 if(dis[v] >= 0) continue; 42 dis[v] = dis[u] + 1; 43 if(v == t) return true; 44 Q.push(v); 45 } 46 } 47 return false; 48 } 49 LL DFS(int now, int t, LL maxflow) //當前在now，匯點t 50 { //最大可以提供maxflow的流量 51 if(now == t) return maxflow; 52 int ret = 0; 53 for(int i = cur[now] != -1 ? cur[now] : pre[now]; i >= 0; i = next[i]) if(edges[i].cap > edges[i].flow) 54 { 55 int v = edges[i].to; 56 if(dis[v] != dis[now] + 1) continue; 57 int l = DFS(v, t, min(edges[i].cap - edges[i].flow, maxflow - ret)); 58 ret += l; 59 edges[i].flow += l; 60 edges[i^1].flow -= l; 61 cur[now] = i; 62 if(ret == maxflow) return ret; 63 } 64 cur[now] = -2; 65 return ret; 66 } 67 LL solve(int s, int t) 68 { 69 int res = 0; 70 while(BFS(s,t)) 71 { 72 memset(cur, -1, n * sizeof(int)); 73 res += DFS(s, t, inf); 74 } 75 return res; 76 } 77 };
?
代碼可能有錯，煩請指出。謝謝。
另外，如果有人知道些好用的畫圖軟件麻煩推薦一下。用windows自帶畫圖太累了。
，如果%util接近 100%，說明產生的I/O請求太多...)
)
