Ford-Fulkerson算法

本文讲解Ford-Fulkerson算法的思路，算法本身与证明，最后会给出模板。Ford-Fulkerson算法是增广路算法的一种，用于求解最大流问题，不明背景请看网络流这篇文章。

分析

朴素算法

朴素的想法（的一种）是这样的：在图中DFS，一旦找到一条从s指向t并且可以在这条路径上添加流量（即：每条边$e$都满足$f_e<w_e$），那么就在这条路径的所有边上同时不断添加流量，直到无法再添加（即：某条边$e$上$f_e=w_e$）。直到无法再找到任何这样的路径，即得到最大流。如下图。

上面的图中，黑色为边的容量，红色为边的容量。图1为原来的网络，其中1为源点，6为汇点。图二为DFS时可能得到的一个图，可以看到上面的算法在这里就会停止。而图三是该网络的最大流。可以轻松地验证这一点，因为从1出发的边都已经满流了，无法再增加新的流量。注意，DFS可能得到最优解，但不是一定得到最优解。

所以上述的算法是错误的。但是它错在哪里呢？

改进

观察图3，这个流比图2多的流如图4：

从图4看，它是把图2中$2\rightarrow4$已有的流量1“推了回去”而产生的。这也正是增广路算法的核心所在。但是，这看起来不可理喻：原图中没有的边，为什么凭空造出来一条就正确呢？

解释

仔细观察图2和图3，就会发现，$4\rightarrow6$的边流量没变，仍然是1。但是，$2\rightarrow4$的流量没有了，那最大流中谁为4提供那一个流量呢？显然是$1\rightarrow3\rightarrow4$的路径。同理，$1\rightarrow2$的流量也没有变，它从$2\rightarrow5\rightarrow6$的路径流出去了。这就可以想象成，节点4不知道是谁给他的流量，也就是在这个过程中4的上游的信息被屏蔽了，同时2的下游的信息也被屏蔽了。只要有人能为4提供流量，他就什么都不知道。同样的，只要有人能从2运走流量，他也什么都不知道。这样，在新的流中，原本只有一份的流量，$1\rightarrow3\rightarrow 4$流走了一份，$1\rightarrow2\rightarrow5$又流走了一份，所以流量+1。

所以，$\langle u,v\rangle$的反向边$\langle v,u\rangle$的意义就是：在$\langle u,v\rangle$有流$f$的时候，如果有一个路径可以从$v$流入（称其前面的那段路经为上游）再从$u$流出（称其后的那段路径为下游）且流为$f_0\le f$，那么就可以认为上游为$v$提供原来的一部分流$f_0$，而从$u$流入的那些$f_0$“改道”从下游流出了。

上面的做法，可以算作对朴素DFS做法的一个修正，大概可以理解为：避免了因DFS顺序不确定而导致的错误。

于是对一个流，可以对图上所有有流$f$的边$\langle u,v\rangle$建立反向边$\langle v,u\rangle$，其容量为$f$。这样得到的新的图称为残余网络，残余网络上从$s$到$t$的路径叫做增广路。在残余网络上进行dfs沿着增广路来添加流，这就是Ford-Fulkerson算法。

算法描述

对网络上的每个流$G(V,E)$，定义与之对应的残余网络$G'(V,E')$：若$f_e>0(e=\langle u,v\rangle\in E)$，那么$e\in E'$且$rev(e)=\langle v,u\rangle\in E'$，并且$w_{rev(e)}=f_e,f_{rev(e)}=0$。$E'$中的元素只有刚才描述的那些。那么算法可以描述为：

Ford-Fulkerson算法

输入：网络$G$（一个图$G(V,E)$，$E$中的边$e$有权重$w_e\in\mathbb{N_+}$），$max\_flow=0$

输出：该网络上的最大流的流量$f$

步骤0. [建立反向边] 定义$max\_flow\gets0$，用邻接表G[V]存储网络；对$E$中的每条边$e=\langle u,v\rangle$，作其反向边$e'=\langle v,u\rangle$，并置$w_{e'}\gets0$。

步骤1. [寻找增广路] 在$G$上DFS，寻找从$s$到$t$的简单路径，要求该路径上每条边可用权值$(w_e-f_e)$大于0。若找到，记该路径上的权值最小的边权值为$f$，否则$f\gets0$。

步骤2. [找到了，更新残余网络] 如果$f>0$，置$max\_flow\gets max\_flow+f$。对路径上的每条边$e$，置$f_e\gets f_e+f$。记其反向边为$e'$，置$w_{e'}\gets w_{e'}+f$。返回1。

步骤3. [没有找到] 如果$f=0$，输出$max\_flow$，算法结束。

最大流不会超过从$s$出发的所有边的边权和。而该算法中每次进入步骤1后，$f$总是正整数（也有$f=0$的情况，此时算法结束），所以该算法对整数总是有限的。若记最大流流量上界为$F$，则该算法最多进入步骤1$(F+1)$次，而每次进入步骤1需要$O(|E|)$的复杂度进行搜索。所以总的时间复杂度是$O(F|E|)$。但这个复杂度上界是很松的，实际用起来效率比较高，所以有时即使估计复杂度偏高也可以使用。对$F$较小的情况则可以轻松应对。

证明

在Ford-Fulkerson算法结束后的残余网络上没有$s\rightarrow t$路径，所以（残余网络上）从$s$可达的所有点构成的集合$S$不包含$t$。记$T=V-S$，那么$T$不空，并且$T\cap S=\varnothing$。

结论1：从$S$指向$T$（满足$u\in S,v\in T$）的边$e=\langle u, v\rangle$都应当满流，即$w_e=f_e$。否则，由于从$s$可达$u$，$s$也可以从$s\rightarrow u\rightarrow v$到达$v$，那么$v\in S$，矛盾。

结论2：从$T$指向$S$（满足$u\in T,v\in S$）的边$e=\langle u,v\rangle$流量必为0。否则，$s$可由其反向边到达$u$；即：流入$S$的流量为0。（反向边就是在这里用到的）

对于任意一个流，$S-\{s\}$中的点流入的流量都等于流出的流量，那么流入$S-\{s\}$的流量$f_{in}$等于从$S$流向$T$的所有边的流量和$S_f$，这个和不超过从$S$流向$T$的所有边的容量和$S_w$，写在一起就是$f_{in}=S_f\le S_w$。从而从$s$流出的流量$f_s$一定不超过$S_w$，因为$f_s$应当是$f_{in}$的一部分。即$f_{s}\le S_w$，这是对任意流的结论。

而对于残余网络（注意残余网络也是一个流），由结论1，$S_f=S_w$。又由结论2，$f_s$即为$f_{in}$的全部，所以有$f_s=f_{in}=S_w$，所以$f_s$为所有流中的最大者。

也可以用反证法。若存在比Ford-Fulkerson算法得到的流更大的流，仍然观察上面的点集$S$，此时从$s$流出的流量$f_{s'}$应当超过了$f_x=S_w$，这时$S-\{s\}$中的点不可能满足流入每个顶点的流量等于流出的流量，所以这样的流不存在。

至此，就证明了Ford-Fulkerson算法的正确性。

模板

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define V 5005 //V为顶点最大个数<span class="bd-box"><h-char class="bd bd-beg"><h-inner>，</h-inner></h-char></span>视数据范围而定
#define INF 0x7fffffffffffffff

using namespace std;
typedef long long ll;
struct edge {
    ll to, w, rev;
};
vector<edge> G[V];
int s, t;//源点和汇点<span class="bd-box"><h-char class="bd bd-beg"><h-inner>，</h-inner></h-char></span>是全局变量
bool vis[V];

ll max_flow();
ll dfs(ll u, ll f);
void add_edge(ll from, ll to, ll w);

ll dfs(ll u, ll f) {
    if(vis[u]) return 0;
    vis[u] = true;
    if(u == t) return f;
    for(int i = 0; i < G[u].size(); i++) {
        edge &e = G[u][i];//注意是引用<span class="bd-box"><h-char class="bd bd-beg"><h-inner>，</h-inner></h-char></span>需要直接修改原图
        if(!vis[e.to] && e.w > 0) {
            ll curf = dfs(e.to, (f > e.w) ? e.w : f);
            //min函数有些编译器不给过
            if(curf > 0) {
                e.w -= curf;
                //直接修改容量而非同时记录f和w<span class="bd-box"><h-char class="bd bd-beg"><h-inner>，</h-inner></h-char></span>只是为了方便
                G[e.to][e.rev].w += curf;
                return curf;
            }
        }
    }
    return 0;
}
ll max_flow() {
    ll maxf = 0;
    while(true) {
        memset(vis, 0, sizeof(vis));
        ll f = dfs(s, INF);
        if(f == 0) break;
        maxf += f;
    }
    return maxf;
}
void add_edge(ll from, ll to, ll w) {
    G[from].push_back(edge(to, G[to].size(), w));
    G[to].push_back(edge(from, G[from].size() - 1, 0));
}

如有发现模板的错误请联系我指正，我将不胜感激。