網路流 何為網路流 想要弄清楚網路流，首先要知道網路的概念，通常在運籌學中，網路是指一個有向圖$G\ =\ (V,E)$ 。其每條邊$(u,v)\in E$都有一個權值$c(u,v)$,稱為這條邊的流量(Capacity)，還有兩個特殊的點，一個是源點(Source),一個是匯點(Sink)在圖論中 ...
網路流
何為網路流
想要弄清楚網路流，首先要知道網路的概念，通常在運籌學中，網路是指一個有向圖$G\ =\ (V,E)$ 。其每條邊$(u,v)\in E$都有一個權值$c(u,v)$,稱為這條邊的流量(Capacity)，還有兩個特殊的點，一個是源點(Source),一個是匯點(Sink)在圖論中，網路流（英語：Network flow）在作為網路的有向圖中分配流，使一條邊的流量不會超過它的容量。
網路流的性質
1.容量限制
$\ \ \ \ $ 對於有向圖\(G\)中的每一條邊上所流經的流量不得超過其容量，即 \(f(u,v) \ ≤ \ c(u,v)\) 。
2.斜對稱性
$\ \ \ \ $ 每條邊的流量與相反邊的流量之和為0，即 \(f(u,v) \ = \ -f(u,v)\)。
3.流守恆性
$\ \ \ \ $ 從源點流出的流量等於匯點流入的流量，即 \(\forall x\in V-\{s,t\},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)\)
$\ \ \ \ $ 現在想象下麵一個情景，工廠里有一個運輸液體的傳輸管道，工廠在每條管道的都設置了防止倒流的裝置，因為壓強問題，所以每條管道在單位時間內的容量有限，這就是一個網路流模型了。
事實上，網路流的應用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及電腦輔助設計等眾多領域。
網路流的常見問題
$\ \ \ \ $ 網路流問題中常見的有以下三種：最大流，最小割，費用流。
最大流
$\ \ \ \ $ 顧名思義，就是求從源點到匯點的最大流量。下麵介紹幾種常見的方法，其中Dinic演算法幾乎能完成所有與最大流相關的問題，因為他的複雜度比較優秀。
Ford-Fulkerson增廣
$\ \ \ \ $ Ford-Fulkerson增廣是計算最大流演算法的一類統稱，核心思想是貪心，通過尋找增廣路來更新並求解最大流。其中，尋找增廣路其實就是尋找從源點到匯點的剩餘容量非空的路徑，對於一條增廣路，我們給每一條\((u,v)\)都加上等量的流量，以令整個網路的流量增加，這一過程被稱為增廣（Augment）。，但是，在執行過程中，會發現這樣的思路有可能導致增廣了一些原來不應存在於最大流的路徑，怎麼辦？
$\ \ \ \ $ 我們可以利用網路流的斜對稱性，在增廣時進行退流操作，如果增廣出了\((u,v)\)之間的雙向流量實際上可以將經過\((v,u)\)的流量交換來抵消成單向流量。
退流操作帶來的「抵消」效果使得我們無需擔心我們按照「錯誤」的順序選擇了增廣路。
接下類就是對Ford-Fulkerson增廣演算法的實現了，對於 Ford–Fulkerson 增廣的不同實現，時間複雜度也各不相同。其中較主流的實現有 Edmonds–Karp, Dinic, SAP, ISAP 等演算法，我會將自己理解了一些的演算法介紹出來，至於其他的，下次一定（doge。
EK演算法(Edmonds–Karp)
演算法思想
EK演算法就是通過BFS不斷尋找增廣路並不斷更新最大流，直至在網路中再也找不到增廣路為止。上面講過，僅僅進行增廣操作的話，最後得到的答案是錯誤的，因此需要退流，而為了追求速度，我們希望能在最短時間找到反向邊，我們發現，利用鄰接矩陣可以快速的找到反向邊，因為鄰階矩陣就具有對稱性，但是因為鄰接矩陣相當於一個二維數組，無論是空間上還是時間上都不是很好，因此在網路流中的通常使用鏈式前向星來存儲。其中，一個常用的技巧是，我們令邊從偶數（通常為 0）開始編號，併在加邊時總是緊接著加入其反向邊使得它們的編號相鄰。由此，我們可以令編號為 \(i\) 的邊和編號為 $i \oplus 1 $的邊始終保持互為反向邊的關係。
存邊代碼如下：
inline void addedge(int u,int v,int c){
edge[++tot].c = c;
edge[tot].to = v;
edge[tot].from = head[u];
head[u] = tot;
edge[++tot].c = 0;
edge[tot].to = u;
edge[tot].from = head[v];
head[v] = tot;
}
更新代碼如下：
inline void update(){
int x = t;
while (x != s){
int v = pre[x];
edge[v].c -= dis[t]; //c是剩餘容量
edge[v^1].c += dis[t];
x = edge[v^1].to;
}
ans += dis[t];
}
適用範圍
時間複雜度為\(O(nm^2)\),一般能處理\(10^3 ~ 10^4\)規模的網路。
完整代碼 \(Code\)
#include <bits/stdc++.h>
#define MAXN 505050
#define int long long
using namespace std;
inline int read(){
int x = 0,f = 1;
char c = getchar();
while (!isdigit(c)){
if (c == '-'){
f = -1;
}
c = getchar();
}
while (isdigit(c)){
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
int n,m,s,t;
int tot = 1,vis[MAXN],pre[MAXN],head[MAXN],flag[2500][2500];
int dis[MAXN];
int ans;
struct node {
int from,to,c,flow;
}edge[MAXN];
inline void addedge(int u,int v,int c){
edge[++tot].to = v;
edge[tot].from = head[u];
edge[tot].c = c;
head[u] = tot;
edge[++tot].to = u;
edge[tot].from = head[v];
edge[tot].c = 0;
head[v] = tot;
}
inline bool bfs(){
for (int i=1;i<=n;i++){
vis[i] = 0;
}
queue<int> q;
q.push(s);
vis[s] = 1;
dis[s] = 2005020600;
while (!q.empty()){
int x = q.front();
q.pop();
for (int i=head[x];i;i=edge[i].from){
int v = edge[i].to;
if (!edge[i].c) continue;
if (vis[v]) continue;
dis[v] = min(dis[x],edge[i].c);
pre[v] = i;
q.push(v);
vis[v] = 1;
if (v == t)return 1;
}
}
return 0;
}
inline void update(){
int x = t;
while (x!=s){
int v = pre[x];
edge[v].c-=dis[t];
edge[v^1].c+=dis[t];
x = edge[v^1].to;
}
ans+=dis[t];
}
signed main(){
n = read(),m = read(),s = read(),t = read();
for (int i=1;i<=m;i++){
int u = read(),v = read(),w = read();
if (flag[u][v] == 0){
addedge(u,v,w);
flag[u][v] = tot;
}
else {
edge[flag[u][v]-1].c+=w;
}
}
while (bfs()!=0){
update();
}
cout<<ans<<'\n';
return 0;
}
Dinic演算法
Dinic演算法在大部分圖上的效率都十分優秀，因此也算是處理網路流問題中較為常見的，其時間複雜度是\(O(|V|^2|E|)\) 因為本人太菜不會證明，故不列出證明(
演算法思想
EK演算法可能會遍歷整個殘量網路（所有邊均為其殘量的 \(G_f(V,E_f)\)）,而只為尋找一條增廣路，顯然只開了單線程，那麼我們能不能找到一種方法，像開多線程一樣，一次尋找多條增廣路呢？
這時候就要我們的Dinic演算法出馬了。
分層圖&\(DFS\)
考慮在進行增廣前先對網路進行\(BFS\)分層，即根據節點到源點的的距離(dis)把節點分成若幹層。對於每一個節點\(u\),我們用\(d(u)\)來表示他的層次，即\(s\)到\(x\)的最少邊數，在殘量網路中，滿足\(d(u) = d(u)+1\)的邊\((u,v)\)構成的子圖被稱為分層圖，而分層圖顯然是一張有向無環圖(Directed acyclic graph)，為什麼要構建分層圖呢？在解釋原因前，要先瞭解Dinic演算法還要通過\(DFS\)進行增廣，在\(DFS\)中,從\(S\)開始，每次我們從下一層的隨機一個點開始跑，就這樣一直跑到匯點，然後再一層層回溯回去，繼續找這一層的另外的點再往下搜索，顯然的，這樣操作可以保證同時多增廣的需求，然後對於每一層的最大流我們再進行合併，就能求出該網路圖的最大流了。
演算法框架
1.在殘量網路上BFS求出節點的層次，構造分層圖
2.在分層圖上DFS尋找增廣路，在回溯時同時更新邊權
適用範圍
時間複雜度為\(O(n^2m)\),一般能處理\(10^4 ~ 10^5\)的網路。
同時，Dinic演算法還能用來求二分圖，複雜度比匈牙利演算法低，但還沒學，所以在這就不介紹了。
代碼 \(Code\)
#include <bits/stdc++.h>
using namespace std;
const long long inf=2005020600;
int n,m,s,t,u,v;
long long w,ans,dis[520010];
int tot=1,now[520010],head[520010];
struct node {
int to,net;
long long val;
} e[520010];
inline void add(int u,int v,long long w) {
e[++tot].to=v;
e[tot].val=w;
e[tot].net=head[u];
head[u]=tot;
e[++tot].to=u;
e[tot].val=0;
e[tot].net=head[v];
head[v]=tot;
}
inline int bfs() { //在慘量網路中構造分層圖
for(register int i=1;i<=n;i++) dis[i]=inf;
queue<int> q;
q.push(s);
dis[s]=0;
now[s]=head[s];
while(!q.empty()) {
int x=q.front();
q.pop();
for(register int i=head[x];i;i=e[i].net) {
int v=e[i].to;
if(e[i].val>0&&dis[v]==inf) {
q.push(v);
now[v]=head[v];
dis[v]=dis[x]+1;
if(v==t) return 1;
}
}
}
return 0;
}
inline int dfs(int x,long long sum) { //sum是整條增廣路對最大流的貢獻
if(x==t) return sum;
long long k,res=0; //k是當前最小的剩餘容量
for(register int i=now[x];i&∑i=e[i].net) {
now[x]=i; //當前弧優化
int v=e[i].to;
if(e[i].val>0&&(dis[v]==dis[x]+1)) {
k=dfs(v,min(sum,e[i].val));
if(k==0) dis[v]=inf; //剪枝，去掉增廣完畢的點
e[i].val-=k;
e[i^1].val+=k;
res+=k; //res表示經過該點的所有流量和（相當於流出的總量）
sum-=k; //sum表示經過該點的剩餘流量
}
}
return res;
}
int main() {
scanf("%d%d%d%d",&n,&m,&s,&t);
for(register int i=1;i<=m;i++) {
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);
}
while(bfs()) {
ans+=dfs(s,inf); //流量守恆（流入=流出）
}
printf("%lld",ans);
return 0;
}
最小割和費用流還沒學完，學完了再寫（
