由於本人太弱，可能講解有誤，請讀者指出。

什麼是網路流

網路流是通過構建從源點到匯點的有向圖模型來解決圖論問題。從理論上講，網路流可以處理所有二分圖問題。
二分圖和網路流的難度都在於問題建模，一般不會特意去卡演算法效率，所以只需要背一兩個簡單演算法的模板就能應付大部分題目了。

最大流問題

什麼是最大流

例題

P3376 【模板】網路最大流

解釋例題

將一些物品從結點 \(s\) 運輸到結點 \(t\)，其中可以通過其他的結點中轉，每條邊都有一條運輸物品上限，求最多有多少物品可以從結點 \(s\) 運輸到結點 \(t\)。

概念

源點：即結點 \(s\)，出發點。
匯點：即結點 \(t\)，結束點。
容量：記 \(c(u,v)\)，從結點 \(u\) 到結點 \(v\) 的邊的運輸物品數量上限，若結點 \(u\) 與結點 \(v\) 之間不存在邊，\(c(u,v)=0\)。
流量：記 \(f(u,v)\)，從結點 \(u\) 到結點 \(v\) 的邊實際運輸物品數量。
殘量：每條邊的容量與流量之差。
由於若將物品從結點 \(u\) 運輸到結點 \(v\)，再又將物品運回來是沒有任何意義的，所以可以規定 \(f(u,v)=-f(v,u)\)。
如圖：每個邊上第一個數是流量，第二個數是容量

性質

通過這些概念，我們就可以從中挖掘出一些性質：

• 容量限制：\(f(u,v)\le c(u,v)\)。
• 斜對稱性：\(f(u,v)=-f(v,u)\)。
• 流量平衡：\(\sum\limits_{u\ne\{s,t\},(u,v)\in E}f(u,v)=0\)。

這是最大流的重要性質，同時也是它的條件。

增廣路演算法

增廣路演算法思想很簡單：從零流開始不斷的增加流量，每一次增加要保持三條性質就行了。
我們通過每一條邊的殘量建邊，對對原有邊建立反向邊，得到一個殘量網路，註意這裡邊的數量可能達到原圖的兩倍：

這樣，我們只需要基於這樣的事實：殘量網路中的任何一條 \(s\) 到 \(t\) 的有向道路都對應著一條原圖中的增廣路。只需要求出該道路中的所有殘量最小值 \(d\)，把所對應的所有邊上的流量增加 \(d\) 即可，這個過程就叫增廣。如圖，紅色的就是一條增廣路。

不難驗證在增廣之後它還是滿足三條性質的。
如果當圖中不存在增廣路時，就說明當前流就是最大流了。
這就是增廣路定理。

實現——Edmonds-Karp 演算法

對於查找路徑，我們可以選用 DFS 或 BFS，但是如果用 DFS 則一不小心就會超時，所以應該選用 BFS來實現，時間複雜度 \(O(nm^2)\)。

Code

int Bfs() {
    memset(pre, -1, sizeof(pre));
    for(int i = 1 ; i <= n ; ++ i) flow[i] = INF;
    queue <int> q;
    pre[S] = 0, q.push(S);
    while(!q.empty()) {
        int op = q.front(); q.pop();
        for(int i = 1 ; i <= n ; ++ i) {
            if(i==S||pre[i]!=-1||c[op][i]==0) continue;
            pre[i] = op; //找到未遍歷過的點
            flow[i] = min(flow[op], c[op][i]); // 更新路徑上的最小值 
            q.push(i);
        }
    }
    if(flow[T]==INF)return -1;
    return flow[T];
}
int Solve() {
    int ans = 0;
    while(true) {
        int k = Bfs();
        if(k==-1) break;
        ans += k;
        int nw = T;
        while(nw!=S) {//更新殘餘網路 
            c[pre[nw]][nw] -= k;
            c[nw][pre[nw]] += k;
            nw = pre[nw];
        }
    }
    return ans;
}

Dinic 演算法

Edmonds-Karp 演算法的劣勢就在於，每次遍歷了一遍殘量網路之後只能求出一條增廣路來增廣。
於是我們針對這一點進行優化，我們就得到了一個更加優秀的替代品，Dinic 演算法。
Dinic 演算法的關鍵就是分層圖和阻塞流。

分層圖

分層圖就是按照結點 \(s\) 到另一個點的最短距離進行分層，相同距離分到一層，就像 \(s\to 第一層\to 第二層\to 第三層\cdots\)。這樣就可以得到每一條這樣的路徑都是 \(s-t\) 最短路。

阻塞流

阻塞流就是指不考慮反向邊的“極大流”。每一次增廣路後將路徑上最小的流量增廣，但是減小，再將那條邊阻塞。


這就是三次增廣後的結果，當圖中不存在 \(s-t\) 路徑，是增廣結束，這就是阻塞流。

時間複雜度

由於最多進行 \(n-1\) 次阻塞流，每次計算不超過 \(O(nm)\)，看上去是總時間複雜度是 \(O(n^2m)\)，但如果是對於二分圖最大匹配這樣的圖，時間複雜度只有 \(O(n^{\frac{1}{2}}m)\)。

Code

struct edge
{
    int to, value, net;
} e[N << 1]; //共有n*2條邊
void add(int from, int to, int value)
{ //鏈式前向星
    cnt++;
    e[cnt].to = to;
    e[cnt].value = value;
    e[cnt].net = head[from];
    head[from] = cnt;
}
int bfs(int st, int ed){ //建立層次圖
    queue<int> que;
    memset(dis, -1, sizeof(dis));
    dis[st] = 0;
    que.push(st);
    while (!que.empty()){
        int x = que.front();
        que.pop();
        for (int i = head[x]; i > -1; i = e[i].net){
            int now = e[i].to;
            if (dis[now] == -1 && e[i].value){
                que.push(now);
                dis[now] = dis[x] + 1;
            }
        }
    }
    return dis[ed] != -1;
}
int dfs(int x, int t, int maxflow){
    if (x == t)
        return maxflow;
    int ans = 0;
    for (int i = cur[x]; i > -1; i = e[i].net){ ///當前弧優化
        int now = e[i].to;
        if (dis[now] != dis[x] + 1 || e[i].value == 0 || ans >= maxflow)
            continue;
        cur[x] = i;
        int f = dfs(now, t, min(e[i].value, maxflow - ans));
        e[i].value -= f;
        e[i ^ 1].value += f; //反向邊加流量
        ans += f;
    }
    if(!ans)dis[x] = -1;
    return ans;
}
int Dinic(int st, int ed){
    int ans = 0;
    while (bfs(st, ed)){
        memcpy(cur, head, sizeof(head));
        int k;
        while ((k = dfs(st, ed, INF)))
            ans += k;
    }
    return ans;
}