网络流 核心知识点收集

本人近期看网络流题，心血来潮，于是决定整理相关核心内容，写了这篇文章。

该文章仍在建设中。作为一名蒟蒻 OIer，本人列出的知识点难免不全，内容也许存在某些疏漏或不当之处，欢迎各位大佬指点。

• 网络流 及其变种
  注：记号约定如下。
  在一般网络流中，边 (u,v,w) 被表示为 u\overset{w}{\to} v。
  在上下界网络流中，令边 u\ \dfrac{\scriptsize c(u,v)}{\scriptsize b(u,v)}\kern{-1.8em}\kern{-.5em}-\kern{-.5em}\longrightarrow v 的流量上界为 c(u,v)，流量下界为 b(u,v)。
  在上下界费用流中，边 (u,v,\dfrac{w1}{w2},c) 表示从 u 到 v、流量上界为 w1、流量下界为 w2、费用为 c 的边。

  • 普通网络流 \Rightarrow Dinic, ISAP, etc。
  • 普通费用流 \Rightarrow 残量网络分层算法由 BFS 改为 SPFA，且要保证 DFS 搜出的增广路径不为环。
  • 有负环的费用流 \Rightarrow 对于所有边 (u,v,\dfrac{w}{0},c)，若 c<0，则将该边替换为 边 (u,v,\dfrac{w}{w},c) 和 边 (v,u,\dfrac{w}{0},-c)，转化为上下界费用流问题。
  • 上下界网络流
  • 无源汇上下界可行流
    1. 令每条边都已经流了 b(u,v) 的流量，设其为初始流。对于原图所有边 u\to v，在新图中加入对应边 u\ \overset{\underrightarrow{\scriptsize{c(u,v)-b(u,v)}}}{ }\ v。
    2. 调整新图。先在新图中加入两个附加点 S',T'。设初始流中，点 u 的 初始流入流量 - 初始流出流量 =M。
       若 M=0，无需附加边。
       若 M>0，即初始入流量过大，在新图中加入附加边 S'\overset{M}{\to} u。
       若 M<0，即初始出流量过大，在新图中加入附加边 u\overset{-M}{\to} T'。
    3. 新图建完后，跑 S' 到 T' 的最大流，要求附加边全部满流。因为只有在这种前提下，新图流量平衡 才能推得 原图流量平衡。若不能保证 S' 连出去的边全部满流，则可行流不存在。
  • 有源汇上下界可行流 \Rightarrow 新图中加入附加边 T\overset{+\infty}{\longrightarrow} S，转化为无源汇问题。
  • 有源汇上下界最大流 \Rightarrow 跑完可行流问题后，删去所有附加边（在实际编写中只需令边 T\to S 及其反边容量为 0），再跑一次从 S 到 T 的最大流。答案为 可行流流量 + 最大流流量。
  • 有源汇上下界最小流 \Rightarrow 跑完可行流问题后，删去所有附加边（在实际编写中只需令边 T\to S 及其反边容量为 0），再跑一次从 T 到 S 的最大流。答案为 可行流流量 - 最大流流量。

• 最大流 相关的 图论问题
  注：边 (u,v,w) 被表示为 u\overset{w}{\to} v；式子中等号两侧表示的量可能省略了单位（是点数还是边数）。

  • 在流网络中
  • 最小割 = 最大流
    方案构造：跑完最大流后，在残量网络上从源点 S 出发，标记所有能访问到的顶点，将这些顶点划分到 S_{mark} 集合，其它点则划分到 T_{mark} 集合。若一条边 (u,v) 满足 u\isin S_{mark} \land v\isin T_{mark}，那么该边即为最小割中的割边。
  • 在 N 个点的二分图中
  • 流网络建模方式：对于任意左部点 u 有 S\overset{1}{\to} u，右部点 v 有 v\overset{1}{\to} T，若 u,v 间原本有连边就有 u\overset{\infty}{\to} v。
  • 最小点覆盖 = 最大匹配 = 最大流 （König 定理）
  • 最大独立集 =N- 最大匹配 =N- 最大流
  • 在 N 个点的点带权二分图中（设点权总和为 W）
  • 流网络建模方式：对于任意左部点 u 有 S\overset{val_u}{\to} u，右部点 v 有 v\overset{val_v}{\to} T，若 u,v 间原本有连边就有 u\overset{\infty}{\to} v。
  • 最小点权覆盖 = 最大匹配 = 最大流
  • 最大权独立集 =W- 最大匹配 =W- 最大流
  • 在 N 个点的 DAG 中
  • 最小路径覆盖\tiny\text{\ (点全覆盖、路径不交)} =N- 拆点二分图上最大匹配 =N- 最大流
  • 最小路径覆盖\tiny\text{\ (点全覆盖、路径}\bold{可重}\text{)} \Rightarrow 将原图做一遍传递闭包，再对新图做 最小路径覆盖\tiny\text{\ (点全覆盖、路径不交)} 问题即可。
  • 最小链覆盖\tiny\text{\ (}\bold{边}{全覆盖)} \Rightarrow 增加新点 p_i，将每条边 u_i\to v_i 改成 u_i\to p_i,p_i\to v_i 两条边。之后对新图做 最小路径覆盖\tiny\text{\ (点全覆盖、路径}\bold{可重}\text{)} 问题即可。
  • 最长反链 = 最小链覆盖 （Dilworth 定理）
  • 在 N 个点的点带权有向图 中
  • 最大权闭合子图 = 所有正权点的点权和 - 最小割
    流网络建模方式：新建 附加源汇点 S,T；对于原图中每个点 u，若 w_u>0 则在新图上连边 S\overset{w_u}{\longrightarrow} u，若 w_u<0 则连边 u\overset{-w_u}{\longrightarrow} T；对于原图中每条有向边 (u,v)，连边 u\overset{+\infty}{\longrightarrow} v。
    方案构造：跑完最小割后，点集 S_{mark} 中除 S 外的点为所选点。
  • 在 N 个点的平面图中
  • 最小割 = 对偶图最短路

• 经典网络流建模

  • 多源多汇建模 \Rightarrow 建立 超级源点 和 超级汇点。（例：二分图最大匹配）
  • 拆点法 本质上是将 点的限制 转化为 边的限制 的一种方法。（例：入点与出点的拆点法、分层拆点法）
  • 染色法 常为 黑白染色 \Rightarrow 二分图上的问题。（例：P3355 骑士共存问题 \to 二分图最大独立集）
  • 最小割建模 常见于 仅两种状态的划分问题。（例：P4313 文理分科）
  • 其它建模：最长 k 可重区间集问题、etc。（这里可能会有 Update）

• 参考资料

  • 【洛谷日报 #427】浅谈网络流的各种建模技巧 by strcmp。
  • 上下界网络流 - OI Wiki。