网络流
概念介绍
- 定义 对于任意一张有向图（也就是网络），其中有 个点、条边以及源点和汇点 然后我们把称为边的容量
- 转化 为了通俗易懂，我们来结合生活实际理解上面网络的定义：将有向图理解为我们城市的水网，有户家庭、条管道以及供水点和汇合点 是不是好理解一点？现在给出一张网络
- 流函数 和上面的$c$差不多，我们把$f(x,y)$称为边的流量，则$f$称为网络的流函数，它满足三个条件：
这三个条件其实也是流函数的三大性质：
- 容量限制：每条边的流量总不可能大于该边的容量的（不然水管就爆了）
- 斜对称：正向边的流量=反向边的流量（反向边后面会具体讲）
- 流量守恒：正向的所有流量和=反向的所有流量和（就是总量始终不变）
- 残量网络 在任意时刻，网络中所有节点以及剩余容量大于00的边构成的子图被称为残量网络
网络流模型可以形象地描述为：在不超过容量限制的前提下，“流”从源点源源不断地产生，流经整个网络，最终全部归于汇点。
最大流
最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。
一种通俗的理解就是：把源点看成是自来水场，汇点看成你家，边就是水管，流量就是水管最多能流多少单位的水。自来水厂源源不断的放水，问你家最多能收到几个单位的水。
首先，我们从一条路径来考虑（如下图）：
显然，最大流为2。我们发现，一条路径的流量是由这条路径的最小值决定的。
Edmonds-Karps增广路算法
时间复杂度。然而实际运用中则远远达不到这个上界，效率较高，一般能处理规模的网络
首先，引入增广路的概念（于二分图的增广路不同）：一条从到的路径，水流流过这条路，使得当前可以到达的流量可以增加。
知道了增广路的概念，就可以很显然的想出一种做法，不断寻找增广路并处理和累加答案，直到找不到增广路，答案就是最大流。
那如何寻找增广路呢？从开始，条件是边权不为0（不为0才能增加流量），当搜到时，就找到了一条增广路。然后，将答案加上这条增广路的流量的最小值，将这条增广路上所有边的流量减掉最小值（因为已经使用了），直到找不到增广路。
这个做法看上去很对，但是他有缺陷，看下图：
显然，有两条增广路，最大流为2。但是，如果找到了这条增广路： ，这幅图就会变成这样子：
最大流就变成了1,对于这个问题，可以通过建立反向边来解决。在建图时加入反向边，流量为0，在流量减去最小值的时候，将反向边加上最小值。那么，上面那幅图就变成了这样：
于是，就可以找到另一条增广路 ，图变成了：
发现成功求出了正确的解。可见，反向边的用处就是标记处理过的边，在有更好情况下把原来的操作给撤销。相当于一个反悔操作。
发现成功求出了正确的解。可见，反向边的用处就是标记处理过的边，在有更好情况下把原来的操作给撤销。相当于一个反悔操作。
小细节：用邻接表存图时，要使第一条边编号为2，且反向边一定要在正向边建完以后就建，这样可以很方便的通过异或1来得到反向边。
代码：
Dinic算法
时间复杂度为。实际运用中远远达不到这个上界，可以说是比较容易实现的效率最高的网络流算法之一，一般能够处理规模的网络。
特别的Dinic算法求解二分图最大匹配的时间复杂度为,实际表现则更快。
在EK算法中，我们发现每次只能找到一条最短路。那能不能一次就找到多条增广路呢？答案是可以。首先，用将图分层。为什么要分层呢？因为这样可以保持找到的多条增广路是最短的。如下图，一次找出了两条增广路。
找到增广路后，用遍历多条增广路更新答案，看上去慢，其实它能一次性处理多条增广路，增加了效率。
Dinic算法不断重复一下步骤，指导残量网络中不能到达
- 在残量网络上求出节点的层次，构造分层图
- 在分层图上寻找增广路，在回溯时实时更新剩余容量。另外，每个点可以流向多条出边，同时还加入了若干剪枝。
费用流
指在水流过水管时，每单位水需要交纳水费（可能为负数，就是水厂要付你钱），求最大流和在流量最大的情况下最小的费用。
显然，还是分层，遍历。那么要修改哪一步呢？
遍历是不用修改的，所以需要修改分层。那么要将分层的修改成什么呢？想到费用，我们第一个想到的就是最短路。
所以，只要将分层的$bfs$改为已经死的（因为不能处理负权），就可以了。