• 最大流算法：Dinic或SAP系列，掌握一种
• 费用流算法：SPFA、zkw费用流（有bug但高效）
• 可行流定义：
  • 容量限制：所有边的流量不高于上界，不低于下界
  • 流量平衡：除源汇外，所有点入流量=出流量

有上下界的可行流求法

• 如果有源汇$s$和$t$，建边$t\to s$，容量（上界）无穷大，无下界。如果没有源汇就跳过这个步骤。
• 建立附加源$s’$和附加汇$t’$ 。
• 对于一条边$i\to j$，上界为$u$，下界为$l$：
  • 将其修改为容量为$u-l$，无下界。
  • 建边$i\to t’$和$s’\to j$，容量为$l$，无下界。
• 原图有可行流当且仅当附加源汇满流
• 原图$i\to j$的流量为新图流量$+l$
• 优化建图：对于每个点$i$，合并和抵消$s’\to i$和$i\to t’$的容量

上下界的进一步理解

• 流量、下界、上界的相对关系：
  流量、上下界之间只有相对关系是有用的，这三个数到底是多少本身没有那么明显的作用。我们只需要关注流量离上界还有多少，离下界还有多少，就能知道这个流还能怎么增。边上存离满流还有多少。
• 附加图相当于：
  • 将所有边流量强制设置为下界
  • 此时破坏流量平衡，但满足了容量限制
  • 再通过附加源汇“消化”掉不平衡的流量
• 是否可以把初始流量强制设置为下界到上界的任意值？
  容量：不变
  流量：x
  下界：不变
  建边：x
• 能否据此提出一个规避掉负环的费用流算法？
  如果一条边费用是负的，就把初始流设成上界。

定义讨论

• 上下界
• 有源汇 vs. 无源汇
• 可行流 vs. 最大流 vs.最小流
  • 有源汇可行流：除了源汇都满足流量平衡，所有边都满足容量限制。
  • 无源汇可行流：所有点都满足流量平衡，所有边都满足容量限制。
  • 有源汇最大流：除了源汇都满足流量平衡，所有边都满足容量限制且从源点出去的流量最大。
  • 无源汇最大流：无源汇没有最大流。
  • 有源汇最小流：除了源汇都满足流量平衡，所有边都满足容量限制且从源点出去的流量最小（反过来求最大流）。
  • 无源汇最小流：所有点都满足流量平衡，所有边都满足容量限制。
• 最小费用流 vs. 最大费用流。
  • 最小费用流：显然。
  • 最大费用流：费用取相反数成最小费用流。
• 最小费用可行流 vs. 最小费用最大流 vs. 最小费用最小流
  • 最小费用可行流：费用最小的可行流。
  • 最小费用最大流：流量最大时费用最小。
  • 最小费用最小流：流量最小时费用最小。
• 有负环的最短路 vs. 有负环的费用流

性质大集合

• 无源汇指定边最大/小流↔有源汇最大/小流
• 源到汇最小流↔汇到源最大流
• 上下界可行流↔附加源汇满流
• 上下界最小流↔上下界可行流+汇到源最大流
• 上下界最大流↔上下界可行流+源到汇最大流
• 最小费用可行流↔ SPFA增流直到源到汇总费用非负
• 最小费用最大流↔ SPFA增流直到源到汇达到最大流

常用建图技巧

• 拆点：限点容、改变费用、划分阶段
• 限定边满流：流量必须为定值的边等于上下界相等
• 重chóng边合并：两个点之间的多条边容量合并
• 分拆重chóng边：不同次经过时产生的费用/收益不同
• 单入边或出边省点：一个点只有一条入边时可能去掉该点
• 满流与下界转化：一条边一定满流时可以对图进行转化