本章代码链接：https://pan.baidu.com/s/1zHHKvvAj3JPNbiDggYSO1g 提取码：mphz
【网络流是什么】
网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。
【概念·容量网络】
容量网络: 设 G(V, E)是一个有向网络, 在顶点集V 中指定了一个顶点, 称为源点(记为 S ), 以及另一个顶点, 称为汇点(记为T); 对于每一条弧∈E, 对应有一个权值 c(u, v)≥0, 称为弧的容量, 通常把这样的有向网络 G 称为容量网络。
【概念·最大流问题】
最大流问题：给定一个有向图G=(V,E)，其中每一条边(u,v)均有一个非负数的容量值，记为c(u,v)≥0。同时在图中有两个特殊的顶点，源点S和汇点T，要求从源点S到汇点T的最大可行流量。
【概念·残余容量】
定义cf(u,v)=c(u,v)-f(u,v)表示边（u,v）的残余容量，意思是该边最多还能通过cf(u,v)的流量。
【概念·残余网络】
由残余容量大于0的边构成的网络
【概念·增广路】
找出一条从S到T的路径p，使得路径p上所有边的cf(u,v)都
大于0。假设路径p上最小的cf(u,v)等于k，那就可以使得S到T增加k
的流量。
【相关规定】
一般，每条有向边上有两个量，容量和流量，从i到j的容量通常用c[i,j]表示,流量则通常是f[i,j].注意，这里的f(i,j)通常认为是净流，也即若i->j实际流量为p，j->i实际流量为q，则f(i,j)=p-q;（例：如果u到v有 4 单位的实际流及由v到u有 3 单位的实际流，那么f(u,v) = 1 及f(v,u) = − 1），
【性质】
- 容量限制：对任意u,v∈V，f(u,v)≤c(u,v)。
- 反对称性：对任意u,v∈V，f(u,v)=-f(v,u).从u到v的流量和从v到u的流量互为相反值。
- 流守恒性：除非u=s或u=t，否则Σf(u,w)=0（w∈V）即结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。
【EK算法】
EK算法，也即最短路径增广算法，基于FF方法（Ford-Fulkerson方法）即增广路方法。
增广路方法是很多网络流算法的基础，一般都在残留网络中实现。其思路是每次找出一条从源点到汇点的能够增加流量的路径，调整流值和残留网络，不断调整直到没有增广路为止。之所以正确是因为FF方法的基础是增广路定理(Augmenting Path Theorem):网络达到最大流当且仅当残留网络中没有增广路。这个思路十分容易理解，也不必证明。
不断地dfs/bfs寻找增广路，记录路径上的边以及路径上所有边中最小的残余容量Min，路径上每条边容量减去Min，总流量加Min。直到无法找到即可。
【Dinic算法】
实际情况中EK算法的效率不理想，所以一般使用Dinic或ISAP等更高效率的算法。EK算法每次寻找增广路都是一条一条找，而Dinic算法则是尽可能寻找多条增广路，实现多路增广。
算法步骤：
对残余网络进行bfs分层，把起点s到结点u的距离d(u)看成u的层次。
dfs增广，增广路沿着满足d[v]=d[u]+1的边（u,v）走。
重复直到找不到增广路。
由于Dinic算法每轮进行一次bfs，然后dfs增广， 每轮结束后源点和汇点不再连通，因此源点到汇点的最短路至少会加1，最多有O(n)轮bfs，每条增广路增广至少使一条边满流，一轮最多增广O(m)次，增广路径长度O(n)，因此复杂度O（n^2 *m）。然而这只是理论最坏复杂度，实际上效率往往更优。如果所有边容量为1，可以证明Dinic算法时间复杂度为O(min(n2/3,m1/2) *m)，对于二分图最大匹配这种特殊图，复杂度为O(n^1/2 *m).
【ISAP算法】
菜鸡没学不知道
【最大流最小割定理】
对于一个网络流图G=(V,E)，其割的定义为一种点的划分方式：将所有的点划分为S和T=V-S两个部分，其中源点s∈S，汇点t∈T。
定义净流f(S,T) = Σf(u,v),u∈S,v∈T。
定义割的容量C(S,T)为所有从S到T的边容量之和C(S,T) = Σc(u,v),u∈S,v∈T。
证明如下：
任意一个割的净流f(S,T)都等于当前网络的流量f，f(S,T) = f(S,V) - f(S,S).
从S到T的流等于从S到所有节点的流减去从S到S内部节点的流，f(S,T) = f(S,V).由于S内部的节点之间存在的流一定有对应的反向流，因此f(S,S)=0，f(S,T)= f(s,V)+f(S-s,V).
再将S集合分成源点s和其他属于S的节点，f(S,T) = f(s,V).
由于除了源点s以外其他节点不会产生流（流量平衡）f(S-s,V)=0，f(S,T) = f(s,V) = f.
那么对于任意ST割有当前流量f=f(S,T)<=C(S,T).
当沿增广路增广的算法找不到增广路时，把源点s能到的点归为S集，剩下V-S为T集，形成一个ST割。且对于任意的u∈S,v∈T，有f(u,v)=c(u,v)（如f(u,v)0，s可以到达v，与v属于T矛盾）。即当前流量f=C(S,T)，f<=任意C(S,T)的等号成立，即此时C(S,T)最小，为最小割，f最大，为最大流。最大流=最小割。
看不懂没关系，因为我也看不懂。
【最小费用最大流】
最小费用最大流，给原来网络每条边加上一个费用值cost，表示每单位流量经过该边需要花费cost，其反向边费用-cost，意思是回流时减少花费（退钱），在求解最大流的前提下，使总费用最小。
解法：每次沿着最小花费的增广路增广（白书有证明）一个简单的算法：Spfa费用流，由于图有负权边，用Spfa寻找最小费用增广路（由于Spfa算法的不稳定，有时可能被卡）
更快的算法：Dijkstra费用流，ZKW费用流。
