网络流初步学习笔记

<前言>

本文为csdn搬运的一篇blog。

嗯，又是挂掉的一天呢。

扯点题外话：今天早上一来，发现人少了一堆，原本的位置都被占了，才知道我被卖了。那些人一声不吭跑去C班寻欢作乐，只留我们寥寥几人不明真相。原本一听网络流我也想溜了，结果一听，mjy老师是从零基础网络流开始讲的，不是很难理解，感觉血赚啊。但是一听C班讲树链剖分，又感觉血亏了。不慌，这波其实不亏。

咳咳，不扯了，开始愉快的网络流初步吧。

<更新档案>

<第一版本>

还未更新过偶

<第二次更新>

8.2的dp听挂了，回来补坑

<第三次更新>

2020.1.17搬运blog，删去部分内容。

<正文>

一开始，m j y老师给了一个形象的例子：网络流就像液体在管道中流动的问题（效率？花费？）以及流水线加工，或许还有交通系统的一系列统一模型的例题

  • 一个流网络 (G=(V,E)) 为一张满足以下条件的有向图：

    • 1.每一条边有一个非负容量，即对于任意E中的 (u,v) , 有(c(u,v)≥0)
    • 2.如果G中存在边 (u,v) ，那么不存在 (v,u) 。我们将图中不存在的边的容量定为0。
    • 3.图中含有两个特殊节点：源 s 与汇 t。

  • 一个流可看做是一个从u到v的映射，满足下面两条性质：

    • 1.容量限制： 对于任意的u,v，(0≤f(u,v)≤c(u,v))

    • 2.流量守恒：对于任何非源汇的中间节点u,我们有
      (sum_{v∈V}f(v,u)=sum_{v∈V} f(u,v))，即流入的流量等于流出的流量，因为节点不可储存流量，所以有进必有出。

那么对于这个玩意，其实也可以很具体的理解。比如说源点就是水龙头，汇点就是下水道。对于中间的每个点，相当于水流沿途的水槽或水管。水槽中可以储存的水是有限的，而且水管中不可储存水，所以流进多少就要流出多少。这就是容量限制和流量守恒了。

令人懵逼的是我并不清楚流量的大小取决于什么，问同学一个高冷的hxc dalao高冷的说“再见”，yjh dalao解释了一堆我没有听懂。现在总之，我知道流量取决于容量大小，取决于要求的两量，s与t。看你怎么跑了。但其实我到现在根本没有写过代码，不过是纸上谈兵罢了，写不来写不来。

最大流

最大流是网络流中一个重要的模型。多种算法都可实现。目前我知道有4个算法，但是老师上课讲了三个。Ford-Fulkerson算法、EK算法、Dinic算法。那么我就来瞎扯几句了。

顺带提一句，已经证明的一个性质：当流量图内没有增广路了，此时的流量图就是最大流了。所以找最大流的过程就是找增广路的过程。（隐藏的重点）

  • 增广路：就是源点到汇点得路径。

  • 残量网络：流量为原图容量-实际流量。对于网络G，其残量网络(G_f)与G的差别在于每条边的边容量修改为G中边容量减去当前流的该边流量。具体来说，(c_j(u,v) = c(u,v)-f(u,v))。
    另外，残量网络中还包含原图中所有边的反向边，容量等同于正向边在f中当前流量，用于“反悔”时将流送回起点：

  • 割：

    • 为一个对于点集V的划分，将V划分为两个集合S与T，其中源点s在S中，汇点t在T中。对于一个流f而言，割（S，T）间的网络流定义为

[f(S,T)=underset{u∈S}{sum}underset{v∈T}{sum} f(u,v)-underset{v∈T}{sum}underset{u∈S}{sum} f(v,u) ]

  • 割（S，T）的容量定义为：

[c(S,T)=underset{u∈S}{sum}underset{u∈T}{sum} c(u,v) ]

  • 对于一个网络而言，最小割为所有的割当中容量最小的那个。

  • 引理1 : 增广后的网络的流量等于两个流流量直接相加。

    证明：
    请自行证明，不会的支持显然法
    a. 是个流（两条性质） b. 流量相同

  • 结论1：增广后流量增加。令(f_p)为当前流f的残量网络中找到的一增广路，则$$left |f↑f_p ight| =|f|+|f_p|>|f|$$

    证明：显然

  • 引理2：对于任意流f，任意割之间的网络流量不变。即$$f(S,T)=|f|$$ 证明：由流量守恒知。

  • 结论2：任意流f的流量不超过任意割的容量。即:

[|f|≤c(S,T) ]

  • 证明：由引理2显然。

  • (|f|=f(S,T))

  • (=underset{u∈S}{sum}underset{u∈T}{sum} f(u,v)-underset{u∈S}{sum}underset{u∈T}{sum} f(v,u))

  • (≤underset{u∈S}{sum}underset{u∈T}{sum} f(u,v))

  • (≤underset{u∈S}{sum}underset{u∈T}{sum} c(u,v))

  • (=c(S,T))

  • 定理1.最大流最小割定理：对于一个网络G，下面三个命题总是等价:

    • 流(f)是(G)的最大流。
    • 当前流 f 的残量网络(G_f)上不存在增广路。
    • 存在某个割使得(|f| = c(S, T))成立。由结论2可知，满足条件的割必定是最小割。

    证明：

    • ((1) -> (2)) 反证法，可由结论1直接导出矛盾。

    • ((2) -> (3)) 构造点集S为s在残量网络上能够到达的点集(T=V-S)，那么t一定在T中，进而(S,T)是一个割。

      考虑S、T间的任意点对(u,v)，如果(u,v)在原网络中存在，那么必定有(f(u,v)=c(u,v))，否则该边会在残量网络中出现从而将u,v放入同一个连通块。

      如果(v,u)在原网络中存在，那么必定有(f(v,u)=0).

      由引理2得，(|f|=c(S,T))。

    • ((3) -> (1))，由结论2知，(|f|<= c(S,T))，故当等号取到时，等式右边必然是最小割，等式左边必然是最大流。

Ford-Fulkerson

根据以上那个性质，所以只要找增广路就行了。本算法使用标记法寻找增广路。这个老师讲的时候我在思（zou）考（shen），没有听到到底怎么找。所以我盲猜一波直接dfs上乱搞，带上个标记别绕圈就行了，当然回溯的时候构建残量图，该变图中数据，根据这个每次寻找修改。

。。。

感觉这么草率结束不太好，那。。。搬一个过程？

1.开始dfs，从源点开始
2.暴力拓展，每次沿出边寻找
3.找到汇点就找到一条增广路
4.回溯，构造残量图
5.重复寻找，知道找不到增广路，即为最大流了

EK算法

  • loding学习中

Ford-Fulkerson算法本身有一个十分致命的缺陷：当答案层数不深，但是无用信息太多时，dfs就明显表现出了缺陷。对于一些刁钻的数据，Ford-Fulkerson显然T飞。

既然无法第一时间找到浅层的答案，那为何不使用bfs搜索来实现呢？这就是EK算法了。

使用bfs可以很方便的确定是否存在增广路，并且可以找到一条进行构建残量图。

但当图十分稠密时，bfs的缺陷又表现出来了，状态数太多，复杂度上天，会T飞的

对于EK算法，老师有一个引理：

  • 引理3 : 在EK算法中，令d(u)表示残量单位网络上从s到u的最短路距离。那么 对于V-{s}中的任意u，在每次增广后d(u)不降。

    • 证明: 考虑两次相邻的增广前后的流，从中选取满足d(u)降的且距离 最近的u进行分析，并导出矛盾。

对于该算法时间复杂度的详细分析证明，在这里，某个最大流算法blog中的EK算法部分有详细介绍。更加详细的介绍也在这，还有代码解析。

结果是该算法复杂度(O(nm^2)),适合稀疏图。

复杂度略证：

  • 定理2: 在EK算法中，增广的次数是(O(nm))的。
    • 证明: 考虑在残量网络的一条增广路中充当“瓶颈”的边，在该次增 广后必定会从残量网络中消失。考虑证明每条边最多消失(O(n))次。加 上一次增广必定会有至少一条这样的边，故最多增广(O(nm))次。
  • 故EK算法的总复杂度为(O(nm^2))

看的出来，其实EK算法的效率其实并没有优秀到哪里去，数据范围稍稍大一点极限级别数据就会使其崩溃。接下来要介绍的几个算法效率都在(O(n^2m))左右更优的有(O(n^2sqrt m))，是十分优秀的，回顾最大流的历史，这几个才是现代信息化以来的成就，在这之前该算法效率一直在EK的水平。

Dinic、SAP、HLPP算法都要用到分层网络。

  • 可行边：在残量网络中，若两个端点间的最短路恰好差1，就称之为可行边。
  • 可行网络：由所有可行边构成的图（最短路图），称为可行网络。
  • 阻塞流：在可行网络上的无法再扩充流量的流，称为阻塞流，注意不必是残量网络的 最大流。
  • 单位容量网络 :所有的存在的边容量均为1的网络

Dinic

说说叫分层网络，名字花里胡哨的，实际上就是bfs然后打一个标记，记录距离源点的距离，这就是所谓的层数了。

从源点出发，bfs知道找到汇点，此时搜索全部停止，不再更新外部节点。将处理过的所有节点构成一个分层网络。

接着用dfs深搜计算累计处理增广路上的节点以及汇点。这样每次处理一遍，每次先一遍bfs找到增广路，在一遍dfs处理。每个这样的操作称为一个阶段。若干个阶段后，直到找不到增广路了，便完成了。

说实话我算法盲，根本发现不了这几个算法有什么区别（|||o_o）。

但是Dinic的优势在于，bfs处理出的很多增广路，可以一次性被dfs处理，这就大大提高李效率。以下是Dinic执行步骤，来自一篇转载的博客：

（1）初始化容量网络和网络流。

（2）构造残留网络和层次网络，若汇点不再层次网络中，则算法结束。

（3）在层次网络中用一次DFS过程进行增广，DFS执行完毕，该阶段的增广也执行完毕。

（4）转步骤（2）。

这个算法老师上课重点讲了，不过她主要是在证明结论计算复杂度什么的，听得我快睡了 。

课后就重新整理了一遍

  • 引理4 : dinic在单位容量网络中至多增广(O(min(E^{frac{1}{2}},V^{frac{2}{3}})))次

  • 证明：

    • a. 增广次数不超过(O(E^{frac{1}{2}}))

      • 分别考虑(d(t)<=E^{frac{1}{2}})和(d(t)>=E^{frac{2}{3}})时的情况 • 前者由于阻塞流增广后的性质，每次自然会增， 因此只需要迭代不超过(E^{frac{1}{2}})次就可到达后一 种情形。

      • 后者考虑层之间的割。由于存在超过(E^{frac{1}{2}})层， 因而必有两层间边数不超过(E^{frac{1}{2}})，由此可推 出残量网络最大流不超过(E^{frac{1}{2}})。由于每次增 广必会增加流量，故只需增广不超过(E^{frac{1}{2}})次。

    • b. 增广次数不超过 (O(V^{frac{2}{3}}))

      • 同理，大家自己思考一下吧。
      • 提示：考虑连续的两层之间的节点个数均不超(V^{frac{1}{3}})前后的情况。

  • 结论3 : dinic在单位容量网络中寻找阻塞流可达(O(E))复杂度。

    证明：依然可以分两部分
    • Dfs调用 — 每个点所在增广路数量之和
    • For循环 — 每条边所在增广路数量之和

    因此，在单位容量网络当中，dinic的时间复杂度可达(O(E imes min(E^{frac{1}{2}},V^{frac{2}{3}})))

SAP、HLPP：

老师没讲啊我也不会。

不过可以给出优质blog的地址：

在这里

说说只有四个算法，但是它讲了5个，还带有例题以及解析。十分不错。

<后记>

列举一下今天的资源网址吧

Dinic：

5种算法：https://blog.csdn.net/yjr3426619/article/details/82808303

markdown使用：https://blog.csdn.net/qq_18150255/article/details/88040858

有时间补坑。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yywxdgy/p/12207506.html