关于网络流
流网络：是一个有向图（可以有环），有两个特殊的点：一个是源点（出发点），一个是汇点，每条边都有属性，叫做容量（也就是每条边的权），
可以想象成一条河，每个点就是一个汇集处，边的容量就是一段的流量。
对于反向边，可以在中间加一个点，所以我们可以默认成不存在反向边
如果边不存在，那容量就是0；
可行流（f），从源点流出，如果满足2个条件就是可行流：1容量限制 2流量守恒（对于每个点，流进多少，就流出多少）
可行流流量值（|f|）=往外流的流量 - 流回来的流量（这里考虑了反向边，但基本上是不需要考虑的）
最大流：即最大的可行流
残留网络：针对流网络的某一条可行流而言，每个可行流都对应唯一的残留网络（Gf）
残留网络的点集就是原网络的点集，边集包括原网络的所有边，和所有反向边，
残留边的容量有两种情况
对于非反向边，也就是图里的边，就是他还没有用掉的容量值，啥意思？？不是说每条边都有一个最大流量吗，那残留网络的边值就是最大流量减去原流量。
对于反向边，就是这条边能退回去多少流量，那也就是这条边的原流量
那为啥要定义这个反向边呢？？对于任意一个点你可以选择走或者是不走，但是你走着走着就发现这条路不是最优解，那你就后悔了于是要返回，返回的流量就是原来流出的流量！！
原网络的可行流（f）和残留网络可行流（f’）有啥关系？
f+f’也是原网络的一个可行流。
证明：那就看是否满足容量限制和流量守恒
分类讨论：如果这两条边的方向是相同的，我们知道残留的最大值就是c（最大容量）-f，也就是说： 0<=f'<=c-f，而原网络的的范围是 0<=f<=c，所以相加的范围就是:0 如果方向不同，那又退回来一些，所以肯定不会超过限制：即：c(u,v)>=f(u,v)+f'(v,u)>=0 第二点就是流量守恒： 那我们可以看出来，反正两边总和是相同的，那就算是相减（反向）还是相加（正向），等号依旧是成立的 就好比 a=b , c=d => a+c=b+d , a-c=b-d 那这个可行流的流量怎么算？ | f + f' | = | f | + | f' | 得到性质：任何一个残留网络的大于零可行流都可以增加原网络里的可行流 换句话说，如果一个残留网络里没有了大于零的可行流，那原网络的可行流就一定是最大的 增广路径： 在残留网络里，从源点出发，沿着容量大于零的边，如果能走到终点的话，这条路径就是一条增广路径（一般不考虑环） 那由定义得，增广路径一定是一条可行流，有何用处？ 割： 将点构成的集合V分成两部分：S和T，要求：S∪T=V，S∩T=?，而且源点s∈S，汇点 t∈T。 那这个划分的结果就是一个割 1、割的容量：所有从S集合指向T集合的边的容量值和(顺序不能换），即c(S,T)= 最小割：割的最小容量 2.割的流量：从S指向T的流量-从T指向S的流量,即： 那就有以下性质：对于任意一个割，割的流量一定小于等于割的容量，即 证明：其实就是考虑不能超过最大流呗 还有，就是我们刚才不是得出了：可行流流量值（|f|）=往外流的流量 - 流回来的流量，那也就是： 那我们再进阶一下： 这个就很好理解了对吧，感性理解一下吧 那现在有个大问题：就是|f|与f（S,T）之间的关系： 来证明一下吧！ $\because S\cup T = V,S\cap T = \phi$ $\therefore f(S,V)=f(S,S)+f(S,T)=0+f(S,T)$ $\therefore f(S,T)=f(S,V)=f(s,V)+f(S-s,V)$ $\because t\notin S,s\notin S-s$ 其实要是是在理解不了（比如我），那就感性理解一下吧！ 当然，还有另一种非常简单的解法(LaTeX在博客园上太太太丑了，所以还是换回来了那个字体）： 然后找到有相同的项的并合并，一约就发现有等于0的部分，然后就OK啦！！！但是由于本蒟蒻精力有限，剩下的证明就不再赘述，请谅解（其实是因为打这玩意真真真太麻烦了） 所以我们得出： 即：最大流<=最小割 下面开始进入核心部分： 关于最大流最小割定定理： 最大流=最小割 首先我们需要知道的是，对于某一个流网络来说：1可行流f是最大流 <=> 2可行流f的残留网络中不包括增广路 <=> 3存在某一个割，使得可行流的流量=割的容量 如何证明？ 首先，如果 f 是最大流，而且残留网络中还有增广路，那么 f 肯定还能加，那 f 就不是最大流了，与前面假设矛盾，所以 1=>2，也就是说如果f是最大流，那f的残留网络一定不包括增广路。 其次，如果有一条可行流，他的流量等于割的容量，假设他不是最大流，那就会存在一条比他大的最大流，那这条最大流的流量一定大于割的容量，由于容量限制，这种情况是肯定不会发生的，所以如果存在一个割，他的容量等于一条可行流的流量，那么这条可行流一定是最大流，所以3=>1，搞定！ 最后，将S集合定义为在残留网络中，从s（源点）出发，沿着容量大于0的可行流走，所有能走到的点，T=V - S，这就是一个合法的割，那么 我们还可以更深一层的发现： 由于可行流一定小于等于割的容量，对于任意的割和流这都是满足的（前提是这个割是可行的），所以我们可以得出：最大流小于等于最小割 又因为最小割<=某一个割的容量c(S,T)=|f|<=最大流，所以最大流大于等于最小割 所以最大流等于最小割 算法：给定流网络，维护残留网络 每次迭代，现在残留网络里找增广路（也就是找一条从头到尾的路径），也就是BFS。之后更新残留网络，就是让原来的残留网络Gf变成Gf+f'。咋更新？举个例子吧！ 假设我现在有一条正向边和一条反向边，设正向边容量为c1，反向边的流量是c2，假设我现在流进了k个单位的流量，那么正向可以流的流量就更新成c1-k，让反向变成c2+k。 就讲到这吧！！！ 拜拜！！！ 
$\therefore t,s\notin S-s$
$设S'=S-s$
$\therefore S'是一个不包括汇点源点的集合，他一定满足流量守恒$
$\therefore f(S',V)=\sum_{u\in S'}^{}\sum_{v\in V}^{}f(u,v)- \sum_{u\in S'}^{}\sum_{v\in V}^{}f(v,u)$
$=\sum_{u\in S'}^{}(\sum_{v\in V}^{}f(u,v)-\sum_{v\in V}^{}f(v,u)$
$=\sum_{u\in S'}^{}(0)$
$=0$
$\therefore f(S,T)=f(s,T)$
$由定义得：f(s,V)=|f|$
$\therefore f(S,T)=|f|$
，设f(x,y)