0

• Ford-Fulkerson for Max Flow
• Min Cut

Ford-Fulkerson for Max Flow

转自最大流问题(Ford-Fulkerson算法)
感谢作者！
侵删。

Ford-Fulkerson

• How we get the min cut
  最后选择capacity = 0 （正向流量已用完）了的paths分割—— min s-t cut.

伪代码如下：
SetFtotal= 0
Repeat until there is no path from s to t:
Run DFS from s to find a flow path to t
Let cp be the minimum capacity value on the path
Add cp to Ftotal
For each edgeu -> v on the path:
Decrease c(u,v) by cp
Increasec(v,u) by cp

Min Cut

定义

对于一个图中的两个节点来说，如果把图中的一些边去掉，刚好让他们之间无法连通的话，这些被去掉的边组成的集合就叫做割了，最小割就是指所有割中权重之和最小的一个割。

最大流最小割定理（max flow/min cut theory）

For any network having a single origin and single destination node,
the maximum possible flow from origin to destination equals the minimum cut value for all cuts in the network.

对于任意一个只有一个源和一个汇的图来说，从源到汇的最大流等于最小割。

Algorithm

Augmenting path

Ford-Fulkerson

Dinic

推荐这个博文：网络流入门—用于最大流的Dinic算法

• 根据残量网络计算层次图。
• 在层次图中使用DFS进行增广直到不存在增广路径。
• 重复以上步骤直到无法增广(具体见下！！)

介绍
思路：每次都不停地用BFS来构造“层次图”，然后用“阻塞流”来增广。这里我特别标出了两个关键词——层次图，阻塞流。

• Layer: Residual graph s to u的距离是dist(u)，那么dist(u)就是结点u的“层次”。
  只保留每个点出发到下一层次的弧，就得到了一张层次"图"。
  Blocking path: 某路径上 流量最小边 的capacity。
  不考虑反向弧时的“极大流”。
  Layer (on Residual graph)
• 该算法第一次就是将上述那条简单路径的所有流量值加上4（这一过程叫“增广”），然后重复原来的过程直到s到t的简单路径不存在为止。
  Time complexity: O(N^2 * M)（N是结点数，M是边数）

This running time is independent from the edges' capacity;
and especially good for some data structure (like dynamic tree).
分析