算法课上又干别的事了，只能下课来补了。

问题介绍

要了解一个算法，首先必须清楚这个算法要解决的问题是什么。有人说，网络流这东西本身还好，难的是把具体问题抽象成网络流。网络流问题的主要难度在于建模。一般来说，看出这题是网络流，这题就差不多了。

网络流问题定义

定义：给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow)。

这句话并不好理解，采用网上的一个通俗的说法：

你家是汇，自来水厂(有需要的同学可以把自来水厂当成银行之类 以下类似)是源

然后自来水厂和你家之间修了很多条水管子接在一起，水管子规格不一，有的容量大，有的容量小

然后问自来水厂开闸放水，你家收到水的最大流量是多少

如果自来水厂停水了，你家那的流量就是0，当然不是最大的流量

但是你给自来水厂交了100w美金，自来水厂拼命水管里通水，但是你家的流量也就那么多不变了 这时就达到了最大流。

这个通俗说法里有个值得注意的地方，就是自来水厂拼命通水，最后通的水量终究还是有限的，这个值与最大流相等。

1.png

基本性质

设C代表每条边的容量，F代表每条边的流量

  • 容量限制: F(x,y)<=C(x,y)
  • 节点性质：流入量与流出量相等。(源和汇例外，因为对于这两个节点无封闭性)
  • 斜对称性：F(x,y)=-F(y,x)

基本算法

FF算法

全称Ford-Fulkerson算法。

基本思想是这样的：
每次用dfs从源到汇找一条可行路径，然后把这条路塞满。这条路径上容量最小的那条边的容量，就是这次dfs所找到的流量。然后对于路径上的每条边，其容量要减去刚才找到的流量。这样，每次dfs都可能增大流量，直到某次dfs找不到可行路径为止，最大流就求出来了。

但是这种想法是错误的，如下图：

2.png

问题出在过早地认为边a →b上流量不为0，因而“封锁”了流量继续增大的可能。(难以理解，这个意思大概是这种情况并不能完全的包含所有路径，因为由斜对称性，容量已满的一条水管其实可以再容纳反向的流量，而这种思想排除了这种情况)

一个改进的思路：应能够修改已建立的流网络，使得“不合理”的流量被删掉。

一种实现：对上次dfs时找到的流量路径上的边，添加一条“反向”边，反向边上的容量等于上次dfs时找到的该边上的流量，然后再利用“反向”的容量和其他边上剩余的容量寻找路径。

个人感觉上述方法并不容易想到，故暂不介绍。(这个可能是该算法的核心了))

残余网络(Residual Network)

在一个网络流图上，找到一条源到汇的路径（即找到了一个流量）后，对路径上所有的边，其容量都减去此次找到的流量，对路径上所有的边，都添加一条反向边，其容量也等于此次找到的流量，这样得到的新图，就称为原图的“残余网络”。

TODO :继续了解FF算法

Edmonds-Karp算法，即最短路径增广算法。

结语

参考：

赏

我很好奇