演算法學習筆記: 網路流

網路流是演算法競賽中的一個重要的模型，它分為兩部分：網路和流。

網路，其實就是一張有向圖，其上的邊權稱為容量。額外地，它擁有一個源點和匯點。

流，顧名思義，就像水流或電流，也具有它們的性質。如果把網路想像成一個自來水管道網路，那流就是其中流動的水。每條邊上的流不能超過它的容量，並且對於除了源點和匯點外的所有點（即中繼點），流入的流量都等於流出的流量。

網路流中最常見的問題就是網路最大流。假定從源點流出的流量足夠多，求能夠流入匯點的最大流量。例如對上面那張網路而言，最大流是5，其中1->3提供2流量，1->2->3提供2流量（這有點像木桶原理，某條路徑的容量是由最窄的一根水管決定的），1->2->4->3提供1流量（注意這裡不是2，因為上條路徑已經佔用了1->2的2單位容量，只剩1單位容量可用）。

解決這個問題最常用的是Ford-Fulkerson演算法及其優化。

Ford-Fulkerson演算法

FF演算法的核心在於找增廣路。何謂增廣路？例如上圖中我首先選擇1->2->3，這是一條增廣路，提供2流量；然後我們相應地扣除選擇路徑上各邊的容量，1->2的容量變成1，2->3的容量變成0，這時的容量稱為殘餘容量。然後我們再找到1->2->4->3這條路徑，按殘餘容量計算流量，它提供1流量（選擇這兩條路的順序可以顛倒）。1->2->4->3也是一條增廣路。

增廣路，是從源點到匯點的路徑，其上所有邊的殘餘容量均大於0。FF演算法就是不斷尋找增廣路，直到找不到為止。這個演算法一定是正確的嗎？好像不一定吧，比如這張圖……

如果我們首先找到了1->2->3->4這條邊，那麼殘餘網路會變成這樣：

現在已經找不到任何增廣路了，最終求得最大流是1。但是，很明顯，如果我們分別走1->3->4和1->2->4，是可以得到2的最大流的。

為了解決這個問題，我們引入反向邊。在建邊的同時，在反方向建一條邊權為0的邊：

我們仍然選擇1->2->3->4，但在扣除正向邊的容量時，反向邊要加上等量的容量。

這時我們可以另外找到一條增廣路：1->3->2->4。

注意看，現在我們同時選擇了2->3和3->2兩條邊，我們可以認為，這兩條邊上的水流抵消了。所以實際上選擇的路徑就是1->3->4和1->2->4。

其實可以把反向邊理解成一種撤銷，走反向邊就意味著撤回上次流經正向邊的若干流量，這也合理解釋了為什麼扣除正向邊容量時要給反向邊加上相應的容量：反向邊的容量意味著可以撤回的量。

加入了反向邊這種反悔機制後，我們就可以保證，當找不到增廣路的時候，流到匯點的流量就是最大流。

用dfs實現的FF演算法時間複雜度上界是 $O(mf)$ ，其中 $m$ 為邊數， $f$ 為最大流：

int n, m, s, t; // s是源點，t是匯點
bool vis[MAXN];
int dfs(int p = s, int flow = INF)
{
    if (p == t)
        return flow; // 到達終點，返回這條增廣路的流量
    vis[p] = true;
    for (int eg = head[p]; eg; eg = edges[eg].next)
    {
        int to = edges[eg].to, vol = edges[eg].w, c;
        // 返回的條件是殘餘容量大於0、未訪問過該點且接下來可以達到終點（遞歸地實現）
        // 傳遞下去的流量是邊的容量與當前流量中的較小值
        if (vol > 0 && !vis[to] && (c = dfs(to, min(vol, flow))) != -1)
        {
            edges[eg].w -= c;
            edges[eg ^ 1].w += c;
            // 這是鏈式前向星取反向邊的一種簡易的方法
            // 建圖時要把cnt置為1，且要保證反向邊緊接著正向邊建立
            return c;
        }
    }
    return -1; // 無法到達終點
}
inline int FF()
{
    int ans = 0, c;
    while ((c = dfs()) != -1)
    {
        memset(vis, 0, sizeof(vis));
        ans += c;
    }
    return ans;
}

要注意，網路流演算法的複雜度是玄學……雖然這個演算法的複雜度上界非常高，但在隨機圖上表現也不算不可接受，至少可以通過洛谷模板題。當然，還有很多優化空間。

Edmond-Karp演算法

其實，EK演算法就是BFS實現的FF演算法。明白這一點後就可以直接看程式碼了：

int n, m, s, t, last[MAXN], flow[MAXN];
inline int bfs()
{
    memset(last, -1, sizeof(last));
    queue<int> q;
    q.push(s);
    flow[s] = INF;
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        if (p == t) // 到達匯點，結束搜索
            break;
        for (int eg = head[p]; eg; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && last[to] == -1) // 如果殘餘容量大於0且未訪問過（所以last保持在-1）
            {
                last[to] = eg;
                flow[to] = min(flow[p], vol);
                q.push(to);
            }
        }
    }
    return last[t] != -1;
}
inline int EK()
{
    int maxflow = 0;
    while (bfs())
    {
        maxflow += flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to) // 從匯點原路返回更新殘餘容量
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
    return maxflow;
}

為什麼在這裡BFS通常比DFS的效果好？因為DFS很可能會「繞遠路」，而BFS可以保證每次找到的都是最短的增廣路。它的複雜度上限是 $O(nm^2)$ ，至少與流的大小無關了，讓人稍微安心了一點……

Dinic演算法

然而，最常用的網路流演算法是Dinic演算法。作為FF/EK演算法的優化，它選擇了先用BFS分層，再用DFS尋找。它的時間複雜度上界是 $O(n^2m)$ 。所謂分層，其實就是預處理出源點到每個點的距離（注意每次循環都要預處理一次，因為有些邊可能容量變為0不能再走）。我們只往層數高的方向增廣，可以保證不走回頭路也不繞圈子。

我們可以使用多路增廣節省很多花在重複路線上的時間：在某點DFS找到一條增廣路後，如果還剩下多餘的流量未用，繼續在該點DFS嘗試找到更多增廣路。

此外還有當前弧優化。因為在Dinic演算法中，一條邊增廣一次後就不會再次增廣了，所以下次增廣時不需要再考慮這條邊。我們把head數組複製一份，但不斷更新增廣的起點。

int n, m, s, t, lv[MAXN], cur[MAXN]; // lv是每個點的層數，cur用於當前弧優化標記增廣起點
inline bool bfs() // BFS分層
{
    memset(lv, -1, sizeof(lv));
    lv[s] = 0;
    memcpy(cur, head, sizeof(head)); // 當前弧優化初始化
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int eg = head[p]; eg; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && lv[to] == -1)
                lv[to] = lv[p] + 1, q.push(to);
        }
    }
    return lv[t] != -1; // 如果匯點未訪問過說明已經無法達到匯點，此時返回false
}
int dfs(int p = s, int flow = INF)
{
    if (p == t)
        return flow;
    int rmn = flow; // 剩餘的流量
    for (int &eg = cur[p]; eg; eg = edges[eg].next) // eg帶引用，跳過已經增廣過的邊,下次增廣直接從這條邊開始循環
    {
        if (!rmn) // 如果已經沒有剩餘流量則退出
            break;
        int to = edges[eg].to, vol = edges[eg].w;
        if (vol > 0 && lv[to] == lv[p] + 1) // 往層數高的方向增廣
        {
            int c = dfs(to, min(vol, rmn)); // 儘可能多地傳遞流量
            rmn -= c; // 剩餘流量減少
            edges[eg].w -= c; // 更新殘餘容量
            edges[eg ^ 1].w += c; // 再次提醒，鏈式前向星的cnt需要初始化為1（或-1）才能這樣求反向邊
        }
    }
    return flow - rmn; // 返回傳遞出去的流量的大小
}
inline int dinic()
{
    int ans = 0;
    while (bfs())
        ans += dfs();
    return ans;
}

值得注意的是，這個演算法如果用在二分圖中複雜度是 $O(m\sqrt n)$ ，優於匈牙利演算法。

這裡再提一下最大流最小割定理。所謂割，就是從網路中選擇一些邊，使得去掉這些邊後，剩下兩個不連通的分別包含源點和匯點的點集。割的大小是這些邊的容量之和。在所有可行的割中，最小的割稱為最小割。

這個神奇的定理只有短短几個字：最大流等於最小割。利用這個定理可以解決不少網路流的問題，在此不作證明，想看證明可以看這裡。

有人會做一個比喻，割就是恐怖分子切斷自來水廠到你家之間的水管（你們恐怖分子就這點志向嗎？），切斷每個水管的代價就是水管的寬度（邊的容量）。然後當代價最小時，從切斷的水管中流出的流量之和就是最大流。

說起來，我有某種直覺，很多定理，例如König定理、Dilworth定理和現在這個最大流最小割定理，它們之間隱約彷彿有種共同點。或許它們背後有什麼共同的數學背景……？當然也可能是我過度聯想（劃掉

這篇文章只介紹了網路流的基礎內容，其實光是求最大流就有很多優化演算法這裡沒有提到。而且，網路流最難的地方其實在於建模，有很多看似毫不相關的題目都可以建立網路流的模型。如果想見識一下，刷一刷網路流24題吧。這篇筆記就先寫到這裡。

Tags: 演算法---------- 演算法基礎：網路流