网络流算法 ​

最大流问题 ​

EK ​

1. 首先考虑将最大流分解成一条一条的路径（增广路）。
2. 显然，最大流的必要条件是没有增广路。
3. 但在有多条增广路时，增广哪一条路？
   • 直接随便一条肯定是错的，这时，需要引入算法的核心：反悔边。
4. 那么，每次增广以后，将路径上的边容量减去流量，其反边加上流量即可。
5. 复杂度不会证。

dinic ​

1. 将EK扩展到多路增广，具体利用了分层图实现。

复杂度 ​

1. dinic增广轮数：
   • 一般图：$n$
   • 值域相关上界：$\sqrt{\sum_{v\in V}\min(\text{入度容量和},\text{出度容量和})}$
2. dinic单次增广：
   • 一般图：$n\cdot m$
   • 值域相关上界：在所有边容量都比较小的时候，好像近似$m$

费用流问题 ​

SSP ​

1. 条件：没有费用为负的圈。
2. 流程：
   • 将反悔边的费用设成负数。
   • 每次寻找费用最少的路径进行增广即可。
3. 具体实现：
   • 利用spfa直接跑最短路。
   • 复杂度：$n\cdot m\cdot f$

Primal - Dual ​

1. 原理和SSP相同，核心在于求最短路部分，用 势能 + dij。
2. 初始势能可以跑spfa赋，然后考虑每次增广完以后如何改变势能。
3. 势能直接加上dis数组即可，证明略。
4. 复杂度：$f\cdot(n + m)\cdot\log m$

有负环的费用流 ​

1. 将所有的负权边强制满流，然后留下反悔边。
2. 这样就让部分点流量不守恒了，所以套上下界的板子。

上下界网络流 ​

整体思路 ​

1. 考虑将下界去掉，即 强制满流到下界，然后改权值为上界 - 下界。
2. 但这样每个点的流量都不一定守恒。
3. 可以先给出一种流使得流量守恒，然后再调整到要求的流。

可行流部分 ​

1. 新建超级源汇，正权点连源点，负权点连汇点，跑最大流。
2. 注意，对于原图有源汇的情况，需要汇点向源点连$\infty$边。
3. 注意判断如果流不满就是无解。

调整部分 ​

1. 将可行流部分建的边都拆掉，然后该怎么样就怎么样。