网络流问题

网络流问题(network flow problem)一类重要的组合优化问题。研究网络流问题实际上是在研究最大流的问题。

概念

很多问题都可以转化成网络流问题，如运输货物时的物流问题，水流问题，匹配问题等等。网络是一个各条边都有权值和方向的图。

网络流问题，一般情况下我们会把各种网络问题抽象成网络流问题，网络流是满足以下性质的网络：每一条边拥有一个最大的容量c，即该条边可以容纳的最大流量，f是流过该边的实际流量，且总有f<=c。对于图中每个顶点（源点和汇点除外）都有流出的流量等于流入的流量。图中只有一个源点一个汇点，且对于源点来说其流入量为0，对于汇点来说流出量为0，源点的流出量等于汇点的流入量，对于最大流问题既是要找出流入汇点的最大流量值。

最大流问题

问题表述：给定一幅图（n个结点，m条边），每一条边有一个容量，现在需要将一些物品从结点s（称为源点）运送到结点t（称为汇点），可以从其他结点中转，求最大的运送量。

在介绍最大流问题的解决方法之前，先介绍几个概念：反向弧，残余网络，增广路径，最大流定理。

反向弧：若从u到v的边的容量为c ，这条边上有流量 f 流过（称为正向弧），则相当于v到u有一条容量为0的边，其流量为- f ，这条边就是反向弧。

反向弧的意义：反向弧的作用是起到有更优决策的时候会使当前选择的弧会自动放弃。反向弧有流量的原因是因为如果刚刚选择了正向弧，下一次如果存在更优策略使这f的流量流入汇点，就可以选择反向弧，将流量 f 撤销。

残余网络：计算出图中的每条边上容量与流量之差（称为残余容量），即可得到残余网络。注意由于反向边的存在，残余网络中的边数可能到达原图中边数的两倍。

举例如下：观察图1，这种状态下它的残余网络如图2所示。

原图

图2残余网络

增广路径：残余网络中任何一条从s到t的有向道路都对应一条原图中的增广路径 —— 只要求出该道路中所有残量的最小值d ，把对应的所有边上的流量增加d 即可，这个过程称为增广。

最大流定理：如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。

这样的话，求解最大流就只需要在残余网络中寻找增广路，直到不存在可以从s流向t 的增广路，此时即为最大流。求解最大流问题的高效算法有 dinic,sap和isap。

最小割最大流定理

割：将原图中所有顶点分成两个集合S和 T = V - S ，其中源点s在集合S中，汇点t在集合T中。如果把”起点在S中，终点在T中的边全部删除，就无法从s到达 t了。这样的集合划分（S,T）称为一个割，它的容量定义为：∑(边( u , v )的容量和)，其中 u ∈ S , v ∈ T ，即起点在 S 中，终点在 T 中的所有边的容量和。（这里所有的边都不包括反向弧）

最小割：图中所有的割中，边权值和最小的割为最小割。

最小割最大流定理：最大流的值为最小割的容量！

如何求最小割：求完最大流后，在残留网络中从源点 s 开始 dfs ，将能到达的点标号（ c - f >0 的边），已标号结点的集合为S，未标号结点集合为 T，则边集[ S , T ]为最小割。

定理证明：

从s运送到t的物品必然通过跨越S和T的边，所以从s到t的净流量等于|f|=f（S,T）=∑f（u，v）≤∑c（u，v）=c（S,T）。(u∈S, v∈T)

注意这里的割（S,T）是任取的，因此得到了一个重要的结论：对于任意s-t流和任意s-t割（S,T）,有|f|≤c（S,T）。

下面来看残余网络中没有增广路的情形。既然不存在增广路，在残余网络中s和t并不连通。当BFS没有找到任何s-t道路，把已标号结点集合看成S，令T=V-S，则在残余网络中S和T分离，因此在原图中跨越S和T的所有弧满载（这样的边才不会存在于残余网络中），且没有从T回到S的流量，因此|f|= c（S,T）成立。

前面说过，对于任意的f和（S,T），都有|f|≤c（S,T）,而此处又找到了一组让等号成立的f和（S,T）。这样便证明了最小割最大流定理。

最小费用最大流问题

在保证最大流的情形下，网络中的边，可能不只有流量还有费用，那么如果我们一方面希望网络拥有最大流，另一方面我们要求费用达到最小，这就是一个费用流的问题了，对于费用流的问题，事实上我们可以这么考虑，首先我们必须要找到的是最大流，另一方面我们需要费用最小，而在找最大流的时候我们总是在寻找增广路来增广，来使得我们能得到一个比现在更大的流，那么另一方面要求费用最小，所以我们可以在寻找增广路的时候找一条费用最小路来增广，而费用我们也可以看成是距离类的东西，也就是这样的话，我们可以用最短路，来找出这样一个最小费用的路来进行增广，而不断增广，即可得到最大流，这样我们就可以得到最小费用最大流。

网络流和费用流中经常会涉及到拆点的操作，将一个点分成入和出，来拆成两个点。例如联合训练赛的第六场第一个题目tour，给出一张图，要求将这个图划分成几个集合，要求每个集合的点的个数大于等于2，要求这个集合所有点可以构成一个环。图中的每条边都有一个边权，最后找到各个集合的总花费为所有构成环的边的权之和。要求这个花费最小。