求解最⼤流的四种算法介绍、利⽤最⼤流模型解题⼊门
上⼀篇中介绍了⽹络流的基础，最⼤流最⼩割定理的证明，下⾯来看如何求⼀个容量⽹络的最⼤流，这⾥介绍四种算法：EK算法、SAP算法、DINIC算法、HLPP算法。这四种算法中，前三种基于增⼴路，最后⼀种基于预流推进。
黑死神
基于增⼴路的算法
怎样修改微信密码Ford-Fulkerson算法
先来简单提⼀下Ford-Fulkerson算法。
在上⼀节中证明了，如果⼀个可⾏流中没有增⼴路，那么此时这个可⾏流的流量就是最⼤流，因此Ford-Fulkerson算法就是在⼀个可⾏流中不断地遍历寻找增⼴路，如果有增⼴路，那么就在这个增⼴路上做调整（前向弧流量增加，后向弧流量减少）来消除增⼴路，当在整个可⾏流中再也没法找到⼀条增⼴路时，就得到了最⼤流。这⼀思想⾮常简单，也很好理解，但问题的关键是：如何在⼀个可⾏流中⾼效地寻找增⼴路？Ford-Fulkerson⽤的是⼀种标号法，但是那种⽅式的时间复杂度可能会依赖于⽹络流中各边的容量，在最坏的情况下复杂度是
O(Ef)(E为边数，f为所有边流量的最⼤值)，例如下图中，如果在查找增⼴路时先选择A->B->C->D，再选
择A->C->B->D，再⾛A->B->C-
>D……如此就需要⾛2000次，⽽实际上直接⾛A->B->D，A->C->D两次就完成了。⽽Furd-Fulkerson算法确实有可能会如前⼀种的⽅式进⾏，因此就不具体介绍了。
EK、SAP、DINIC算法都基于这样的消除增⼴路的思想，但它们给出了更好的查找增⼴路的⽅式，下⾯来分别来看这三种算法。
EK算法
最简单的算法莫过于暴⼒搜索，⽽EK算法正是如此。
在每次搜索增⼴路的时候，都采取BFS的策略，将所有的从源点到汇点的路径都找出来，那么如果有增⼴路，就⼀定可以将它找出来。因此采⽤BFS策略⾸先是正确的，来看⼀下它的代码实现：
//capacity：容量
//flow：流量
//parent：记录在⼀条增⼴路中每个节点的前⼀个节点
//alpha：记录在增⼴路中当每个节点所能调整的流量的最⼤值
int EK(int m)
CHICCA
{
//初始化操作
int result = 0;
for (int i = 1; i <= m; i++) parent[i] = alpha[i] = 0;
queue<int> vertexQueue;
while (true)
{
memt(alpha, 0, sizeof(alpha));
alpha[1] = INF;
vertexQueue.push(1);
//BFS过程
while (!pty())
{
int vtop = vertexQueue.front();
vertexQueue.pop();
for (int i = 1 ; i <= m ; i ++ )
{
//如果⽬标节点还未在增⼴路中出现并且可以调整流量
if (!alpha[i] && flow[vtop][i] < capacity[vtop][i])
{四大滴定
parent[i] = vtop;
alpha[i] = min(capacity[vtop][i] - flow[vtop][i], alpha[vtop]);
vertexQueue.push(i);
}
}
我是真的受伤了}
//汇点可调整流量为0，说明没有增⼴路了，算法结束
if (alpha[m] == 0)
{
return result;
}
//汇点可调整流量不为0，那么找到了增⼴路，增⼴路上所有节点做流量调整
for (int i = m; i != 1; i = parent[i])
{
flow[parent[i]][i] += alpha[m];//前向弧流量增加
flow[i][parent[i]] -= alpha[m];//后向弧流量减少
}
//由于⼀开始流量都为0，调整多少能量就代表整个可⾏流的流量增加了多少
result += alpha[m];
}
}
那么如何评估它的性能呢？⾸先可以确定的是，它不会出现像Ford-Fulkerson那样的问题，考虑上⾯那张图所⽰的情形，如果采⽤EK算法，是肯定不会⾛A->B->C->D的，为什么？因为采⽤BFS获取的路径⼀定是最短距离的路径，很明显上图中从源点到汇点的最短距离为3，因此EK算法能够避免Ford-Fulkerson遇到的问题。
但是仅仅如此还是不能对EK算法的性能有⼀个清晰的认识，需要知道其准确的时间复杂度。不妨先来看⼀个EK算法的运⾏实例：（图来⾃wiki）
红⾊的路径就是每次BFS所找到的增⼴路。从这张图中可以观察到⼀个事实：在每次BFS查找增⼴路之后，最短增⼴路的长度⼀定是⾮减的，也即对于每⼀个节点，它到源点的最短距离是⾮减的。这个
性质可以有严格的证明，见《算法导论》（引理26.7 P426），直观上想象⼀下，如果对于⼀个给定的图确定了从源点到某⼀点的最短距离为，现在在这个图中去掉⼀些边，那么从源点到这⼀点要么变得不连通，要么距离会不变，要么距离会增⼤，绝对不可能减少。因为如果它减少为，那么把去掉的这些边加回来，得到原图，这⼀过程并没有影响到的这条路径，因此原图中还肯定存在距离为的路径，这与为最短距离⽭盾。增⼴路调整的过程，就相当于在原图中去掉了⼀些边，因为某些前向弧变成了满流，后向弧变成了零流，没办法再经过这些边了。
基于这⼀点，可以证明⼀个引理：
鲍鱼的做法有哪几种EK算法中所能找到的增⼴路的数量为O(VE)
证明：
每次调整增⼴路的时候，所调整的流量为所有边可调整流量的最⼩值，那么就定义具有最⼩值的那条边为 关键边，显然每条增⼴路都必须⾄少有⼀条关键边
设流f的源点为s，汇点为t，假设边(u,v)成为某次BFS搜索得到的增⼴路中的关键边，此时，在这次增⼴路流量调整后，这条边的可调整流量将变为0，也就是说(u,v)会从残存⽹络中消失。如果边(u,v)想要再度成为关键边，那么(u,v)的流量必须要减少，也就是说当(u,v)再度成为关键边时⼀定有，⽽⼜有，
因此，也就是说当边两次成为关键边时，⾄少增加2。⽽(为顶点总数)，因此边成为关键边的次数⾄多为即，整个图中所有的边理论上都有可能成为关键边，因此所有边成为关键边的次数⾄多为，每条增⼴路⾄少有⼀条关键边，因此增⼴路的数量⾄多为，引理得证。
由于BFS找增⼴路的时间复杂度为，⽽⾄多进⾏次查找，因此就可以得出EK算法的时间复杂度为EK算法的代码实现很简单，当整个图是稀疏图的时候，使⽤EK算法不失为⼀种简便可⾏的⽅法，但是如果图的边数⾮常多，这个算法的性能也就显得不是那么优秀。可以看到EK算法的处理在每次找到增⼴路后，就从源点开始重新再BFS遍历查找，这⼀过程中有很多的遍历都是没必要的。
d d <′d d ′d ′d dist (s ,v )=dist (s ,u )+1dist (s ,u )=′dist (s ,v )+′1dist (s ,u )>′=dist (s ,u ),dist (s ,v )>′=dist (s ,v )dist (s ,u )>′=dist (s ,u )+2(u ,v )dist (s ,u )dist (s ,u )<=∣V ∣−2∣V ∣(u ,v )O ()2∣V ∣−2O (∣V ∣)O (V E )O (V E )O (E )O (V E )O (V E )
2
在后⾯这三种算法的介绍中，它们都⽤到了⼀个共同的结构：分层⽹络。
其实也就是做⼀次BFS，先对源点标号为1，然后遍历源点的相邻节点，标号为2，再遍历这些节点的相邻节点……下⾯来介绍Dinic算法：
1.将源点的层次设为1，其余层次初始化为0。
2.沿着⾮饱和前向弧和⾮零流后向弧构造层次⽹络，如果发现汇点不在层次⽹络中则算法终⽌。
3.在层次⽹络中，沿着相邻层搜索所有的增⼴路，并做相应的流量调整，回退到1。
来看⼀个具体的求解实例：(图来⾃wiki)
第⼀次建⽴层次⽹络，找到了蓝线表⽰的三条增⼴路，做流量调整
第⼆次建⽴层次⽹络，边(s,1) (1,3) (1,2)均不在建⽴层次⽹络中起作⽤，找到⼀条增⼴路。
第三次建⽴层次⽹络，汇点不在层次⽹络中，算法终⽌。
Dinic算法的代码实现为：
void bfs()
{
memt(visit, fal, sizeof(visit));
memt(dist, 0, sizeof(dist));
queue<int> vertQue;
vertQue.push(1);
dist[1] = 0;
visit[1] = true;
while (!pty())
{
int vTop = vertQue.front();
vertQue.pop();
for (int i = head[vTop] ; i != -1 ; i = Edges[i].next)
{
//⽬标节点还未被确⽴层次，并且可以到达⽬标节点，就进⾏层次更新 if (Edges[i].capacity && !visit[Edges[i].to])
{
dist[Edges[i].to] = dist[vTop] + 1;
visit[Edges[i].to] = true;
vertQue.push(Edges[i].to);
}中国直销公司排名
}
}
}
//dfs查找所有增⼴路并做流量调整
int dfs(int end , int u , int delta)
{
if (u == end) return delta;
int res = 0;
for (int i = head[u] ; i != -1 ; i = Edges[i].next)
{
if (dist[Edges[i].to] == dist[u] + 1)
{
int dd = dfs(end, Edges[i].to, min(Edges[i].capacity, delta));
Edges[i].capacity -= dd; //前向弧流量增加(capacity为可调整流量)
Edges[i ^ 1].capacity += dd; //反向弧流量减少
delta -= dd;
普法考试系统res += dd;
}
}
return res;
}
int dinic(int end)
{
int ret = 0;
while (true)
{
bfs();
if (!visit[end])
{
return ret;
}
ret += dfs(end, 1, 1e8);
}
return ret;
}
