最大流算法

定理

增广路定理

对于流 $f$，若残留网络 $G_f$ 不存在增广路，则 $f$ 为流网络 $G$ 的最大流。

最大流最小割定理

定义流网络 $G$ 的切割(cut)，为流网络的点集 $V$ 的一个划分 $[S, T]$，且源点 $source$ 在 $S$ 中，汇点 $sink$ 在 $T$ 中。从 $S$ 到 $T$ 的边称为割边。切割的流量即从 $S$ 到 $T$ 的边的流量之和。在网络 $G$ 中 $[S, T]$ 为最小的切割，$f$ 为最大流，则有 $|S| = |f|$。

枚举算法

以最小割最大流定理为基础，可以通过求解最小割的方法来求解最大流。具体思路是枚举个点在 $S$ 中还是在 $G$ 中，算出所有情况流量的最小值，即为流网络的最大流量。不难分析出枚举算法的时间复杂度为 $O(2^{|V|} \times |E|)$。

枚举算法具体实现如下：

/**
 * Enumeration algorithm.
 * source = 0, sink = n-1.
 */
int maxflow() {
    int flow = 0x7fffffff;
    // enumerate all cut (S set).
    for(int state = 0; state <= (1<<(n-2)); ++state) {
        int s = (state<<1)|1, tmp=0;
        for(int u = 0; u < n-1; ++u) {
            for(int v = 1; v < n; ++v) {
                if((state>>u)&1 == 1 && (state>>v)&1 == 0) {
                    tmp += c[i][v];
                }
            }
        }
        flow = flow > tmp ? flow : tmp;
    }
}

增广路算法

根据增广路定理，不难想到，不断在残余网络中寻找增广路进行增广，直到找不到增广路为止。即可求解出源点和汇点之间的最大流量。可以通过以下几种方式来寻找增广路。

深度优先搜索

只要残余网络中还存在增广路，那么对网络流图每进行一次DFS遍历，便可以找到一条从源点到汇点的增广路。若为整数网络，则找到的增广路的流量至少为 $1$，因此，算法复杂度为 $O(|E| \times c)$ ($c$为最大流量)。

算法实现：

int dfs(int x, int low) {
    if(x == sink) {
        return low;
    }
    if(vis[x]) { // 有环
        return 0;
    }
    vis[x] = true;
    for(int i = 0, flow = 0; i < n; ++i) {
        if(c[x][i] && (flow = dfs(x, low<?c[x][i]))) {
            c[x][i] -= flow;
            c[i][x] += flow;
            return flow;
        }
    }
    return 0;
}

int maxflow() {
    int flow = 0, tmp;
    memset(vis, 0, sizeof(vis));
    while(tmp = dfs(s, 0x7fffffff)) {
        memset(vis, 0, sizeof(vis));
        flow += tmp;
    }
    return flow;
}

使用深度优先策略寻找增广路时，可以使用当前弧优化。即记录每个节点当前已经枚举到了哪个节点，下一次搜索时从当前节点开始搜索。

实现时，只需要用一个额外的数组记录当前弧(current arc)即可。

int dfs(int x, int low) {
    if(x == sink) {
        return low;
    }
    if(vis[x]) { // 有环
        return 0;
    }
    vis[x] = true;
    for(int ii = 0, i = cur[x], flow = 0; ii < n; ++ii, i = (i+1==n?0:i+1)) {
        if(c[x][i] && (flow = dfs(x, low<?c[x][i]))) {
            cur[x] = i;
            c[x][i] -= flow;
            c[i][x] += flow;
            return flow;
        }
    }
    return 0;
}

广度优先搜索

采用广度优先搜索的策略来寻找增广路径，不难证明最多只需要 $O(|V| \times |E|)$ 次增广，每次寻找增广路径的复杂度为 $O(|E|)$。因此，算法总复杂度为 $O(|V| \times |E|^2)$。这便是求解最大流问题的Edmond-Karp算法。

实现：

int maxflow() {
    int u, v, l, r, flow(0);
    do {
        memset(vis,0,sizeof(vis)) ; vis [source]=1;
        memset(a,0,sizeof(a));low[s]=2147483647;
        q[0]=source; l=0; r=1;
        while(l<r) {
            u=q[l++];
            for(v=1; v<=n; v++) {
                if(!vis[v] && c[u][v]>f[u][v]) {
                    vis [v]=1; pre[v]=u; q[r++]=v;
                    low[v]=c[u][v]−f[u][v];
                    if(low[v]>low[u]) {
                        low[v]=low[u];
                    }
                }
            }
        }
        if (low[sink]>0) {
            u=t;
            do {
                f[pre[u]][u]+=low[sink];
                f[u][pre[u]]−=low[sink];
                u=pre[u];
            } while(u!=s);
            ﬂow+=low[sink];
        }
    } while(low[sink]>0);

    return ﬂow;
}

标号法(SAP)

SAP, Shorest Argument Path，最短增广路算法。

与EK算法相比，SAP算法引入了距离标号，用一个 $dis$ 数组来表示每个节点距汇点的最短距离。距离标号 $dis$ 数组满足以下两个条件：

$dis[sink] = 0$；
对于残留网络中的一条弧 $(u, v)$ 有 $dis[u] \leq dis[v] + 1$。

对于残留网络中的一条弧 $(u, v)$ 满足 $dis[u] = dis[v]+1$，则称弧 $(u, v)$ 为允许弧。由允许弧组成的一条从源点到汇点的路径称为允许路径。不难分析出允许路径是残留网络中的一条最短增广路。应用标号算法每次增广只需要 $O(V)$ 的时间。因此，SAP算法的时间复杂度为 $O(V^2 \times E)$。

SAP算法的优化

最短增广路算法还有两个重要且有效的优化。

Gap优化

注意到对残留网络中 $dis[u]$ 值得修改只会让 $dis[u]$ 的值越变越大，因此，对于每个节点，$dis$ 值是单调变化的。假如现在有 $dis[u]=k+1$ 而没有一个点使得 $dis[v]=k$，那么意味着出现了断层，也就是说无法再找到一条增广路径。

使用一个 $gap$ 数组记录 $dis$ 数组中每个值由多少个。一旦出现某个 $gap[k]=0$，则算法结束。

当前弧优化

由于 $dis$ 数组的单调性，在查找允许弧时只需要从上一次找到的允许弧开始找即可。

最后，给出SAP最短增广路算法的代码实现：

int sap(int start, int end, int cnt) {
    int u = pre[start] = start, maxflow = 0, aug = -1;
    gap[0] = cnt;
    while(dis[start] < cnt) {
        bool find = false;
        for(int v = cur[u]; v <= cnt; ++v) { // 当前弧优化
            if(maze[u][v] && dis[u] == dis[v]+1) {
                if(aug == -1 || aug > maze[u][v]) {
                    aug = maze[u][v];
                }
                pre[v] = u;
                u = cur[u] = v; // 记录当前弧
                if(v == end) {
                    maxflow += aug;
                    for(u = pre[u]; v != start; v=u,u=pre[u]) {
                        maze[u][v] -= aug;
                        maze[v][u] += aug;
                    }
                    aug = -1;
                }
                find = true;
                break;
            }
        }
        if(find == false) {
            int mindis = cnt-1;
            for(int v = 1; v <= cnt; v++) { // 更新 dis
                if(maze[u][v] && mindis > dis[v]) {
                    cur[u] = v;
                    mindis = dis[v];
                }
            }
            if((--gap[dis[u]])==0) { // gap 优化
                break;
            }
            gap[dis[u]=mindis+1]++;

            u = pre[u];
        }
    }
    return maxflow;
}

预流推进算法

Dinic算法和层次图

最小费用最大流

关于费用流的求解，只需要把EK算法中寻找增广路的过程换成用SPFA求解最短路（权值）的过程即可。

最大费用最大流

将每条边的费用取相反数，再求解最小费用最大流，求得的费用的相反数为最大费用，求得的最大流量为最大流。

网络流模型解决二分图匹配问题

最大流与最大二分图匹配

不难想到，通过限制每个点的流量不超过 $1$ 即可以保证每个点最多只使用一次。实现时，增加一个源点和汇点。从源点到左边集合中每个点连边，从右边集合中每个点向汇点连边，容量都为 $1$。这样，求得的从源点到汇点的最大流量便是原图的最大二分匹配。

费用流与最优（最大权/最小权）二分图匹配

原图中每条边的容量为 $1$。增加一个源点和一个汇点，从源点向左边集合中每个点连边，容量为 $1$，权值为 $0$，从右边集合中每个点向汇点连边，容量为 $1$，权值为 $0$。然后，求解从源点到汇点的最大费用最大流即可得到最大权二分图匹配，求解最小费用最大流即可得到最小权二分图匹配。

定理