だから僕らは がんばって挑戦だよね

网络流常见建模

  • ~4.23K 字
  1. 1. 目录
  2. 2. 网络流模型
    1. 2.1. 最大流最小割
      1. 2.1.1. 最小割树
        1. 2.1.1.1. Gomory-Hu 算法
        2. 2.1.1.2. 参考&例题
      2. 2.1.2. 平面图最小割
        1. 2.1.2.1. 平面图
        2. 2.1.2.2. 对偶图
        3. 2.1.2.3. 对偶图的性质
        4. 2.1.2.4. 参考&例题
    2. 2.2. 费用流
      1. 2.2.1. SSP 算法
        1. 2.2.1.1. 实现
        2. 2.2.1.2. 参考&例题
      2. 2.2.2. 有负圈的费用流
        1. 2.2.2.1. 例题
    3. 2.3. 上下界建模
      1. 2.3.1. 无源汇上下界可行流
      2. 2.3.2. 有源汇上下界可行流
      3. 2.3.3. 有源汇上下界最大/小流
        1. 2.3.3.1. 最大流
        2. 2.3.3.2. 最小流
        3. 2.3.3.3. 例题
  3. 3. 经典问题
    1. 3.1. 二分图
      1. 3.1.1. 二分图最大匹配
      2. 3.1.2. 二分图最小点覆盖
      3. 3.1.3. 二分图最大独立集
        1. 3.1.3.1. 参考
    2. 3.2. 路径覆盖与链覆盖
      1. 3.2.1. DAG 最小路径覆盖
      2. 3.2.2. DAG 最小链覆盖
      3. 3.2.3. DAG 最长反链
    3. 3.3. 最大权闭合子图
      1. 3.3.0.1. 例题
  4. 3.4. 最大密度子图
    1. 3.4.0.1. 例题
  • 3.5. 各种建模
    1. 3.5.1. 拆点

    • 本文主要讲建图方法，定义和证明内容较少。

    正好网络流二十四题做完了整理下。

    目录

    • 网络流模型
      • 最大流最小割
        • 最小割树
        • 平面图最小割
      • 费用流
        • SSP 算法
        • 有负圈的费用流
      • 上下界建模
        • 无源汇上下界可行流
        • 有源汇上下界可行流
        • 有源汇上下界最大/小流
    • 经典问题
      • 二分图
        • 二分图最大匹配
        • 二分图最小点覆盖
        • 二分图最大独立集
      • 路径覆盖与链覆盖
        • DAG 最小路径覆盖
        • DAG 最小链覆盖
        • DAG 最长反链
      • 最大权闭合子图
      • 最大密度子图
    • 各种建模
      • 拆点
      • 分层图
      • 最大流相关
      • 最小割相关
        • 最小割离散变量模型（切糕）
      • 费用流相关
      • 杂
        • 区间问题常见建模

    网络流模型

    最大流最小割

    最大流 = 最小割是网络流中的重要结论，运用最大流和最小割可以解决一些复杂度划分问题。

    最小割树

    主要解决 多次询问 无向图两点之间的最小割的问题。

    一个 NN 个点的图上，两点之间只有 NN 中本质不同的最小割。因此一定存在一棵树，满足树上两点的最小割等于原图上两点的最小割。我们把这样的树称之为 最小割树。

    Gomory-Hu 算法

    考虑分治，在所有点中任取两个作为源汇点求出最小割，划分成两个互不连通的割集。对这两个点连边，边权为求出来的最小割。然后对与两个割集递归下去做。同时每次的最小割都是对于全局跑的，

    询问两个点之间的最小割，就是求这两个点在最小割树上的路径中最小的边。可以用倍增实现。

    参考&例题

    P4897【模板】最小割树

    证明见 Eznibuil 博客

    平面图最小割

    平面图最小割 = 对偶图最短路。

    平面图

    如果图 GG 能画在平面 SS 上，且除顶点外无边相交，则称 GG 可平面嵌入 SS，GG 可称为可平面图或平面图，画出的没有边相交的图称为 GG 的平面表示或平面嵌入。

    对偶图

    设 GG 是平面图的某一个平面嵌入，构造图 G∗G^*：

    1. 在 GG 的每个面放 RiR_i 置 G∗G^* 的一个顶点 v∗v^*。
    2. 设 ee 为 GG 的一条边，若 ee 在 GG 的面 RiR_i 和 RjR_j 的公共边上，做 G∗G^* 的边 e∗e^* 与 ee 相交，且 e∗e^* 连接 G∗G^* 的顶点 vi∗,vj∗v_i^*,v_j^*，即 e∗=(vi∗,vj∗)e^*=(v_i^*,v_j^*)，e∗e^* 不与其他边相交。若 ee 为 GG 中的桥且在 RiR_i 的边界上，则 e∗e^* 是以 RiR_i 中顶点 vi∗v_i^* 为端点的环，即 e∗=(vi∗,vj∗)e^*=(v_i^*,v_j^*)。

    形象化的说，对偶图就是把平面图的每条边 旋转了 9090 度。

    对偶图的性质

    1. G∗G^* 为平面图，且为平面嵌入。
    2. GG 中自环对应 G∗G^* 桥，GG 中桥对应 G∗G^* 自环。
    3. G∗G^* 是连通的。
    4. 若 GG 的面 Ri,RjR_i,R_j 的边界上至少有两条公共边，则关联
      vi∗,vj∗v_i^*,v_j^* 的边有平行边，G∗G^* 多半是多重图。
    5. 同构的图的对偶图不一定是同构的。
    6. G∗∗G^{**} 与 GG 同构当且仅当 GG 是连通图。
    7. 平面图最小割 = 对偶图最短路

    参考&例题

    P2046 [NOI2010] 海拔

    oi-wiki

    费用流

    可以解决一些需要最优化的问题。

    SSP 算法

    每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。

    如果图上存在单位费用为负的圈，SSP 算法正确无法求出该网络的最小费用最大流。

    设该网络的最大流为 ff ，则最坏时间复杂度为 O(nmf)O(nmf)。SSP 算法是 伪多项式时间 的。

    实现

    只需将 EK 算法或 Dinic 算法中找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。

    参考&例题

    P7173【模板】最小费用最大流

    oi-wiki

    有负圈的费用流

    由于存在最短路，所以费用流算法不能直接做费用有负圈的图。

    消圈算法本身就有消除负圈的过程，但是效率低下。

    对于网络中的负费用边 (x,y)(x,y)，强制满流。然后加入 (y,x)(y,x)，费用为原来费用的相反数，用于退流。

    跑有源汇上下界最小费用最大流即可。

    例题

    P7173 【模板】有负圈的费用流

    上下界建模

    上下界网络流本质是给流量网络的每一条边设置了流量上界 c(u,v)c(u,v) 和流量下界 b(u,v)b(u,v) 。也就是说，一种可行的流必须满足 b(u,v)≤f(u,v)≤c(u,v)b(u,v) \leq f(u,v) \leq c(u,v) 。同时必须满足除了源点和汇点之外的其余点流量平衡。

    无源汇上下界可行流

    先假设每条边已经流了 b(u,v)b(u,v) 的流量，在新图中加入流量为 c(u,v)−b(u,v)c(u,v)-b(u,v) 的边。

    最大流需要满足初始流量平衡条件，但是构造出来的初始流很有可能不满足初始流量平衡。

    假设一个点初始流入流量减初始流出流量为 MM，同时建立附加源点 S′S' 和附加汇点 T′T'：

    • M=0M=0 流量平衡
    • M>0M>0 入流量大，SS 向其连流量为 MM 的边
    • M<0M<0 出流量大，其向 TT 连流量为 −M-M 的边

    如果附加边满流，说明这一个点的流量平衡条件可以满足，否则这个点的流量平衡条件不满足。

    在建图完毕之后跑 S′S' 到 T′T' 的最大流，若 S′S' 连出去的边全部满流，则存在可行流，否则不存在。

    有源汇上下界可行流

    设源点为 ss，汇点为 tt。添加一条 tt 到 ss 的上界为 ∞\infty 下界为 00 的边。

    注意这里的源汇点已被视为普通点，与超级源汇点不同的。

    有源汇上下界最大/小流

    最大流

    先找到可行流，然后删去附加边 t→st \rightarrow s，在残留网络上跑最大流。

    将可行流流量和最大流流量相加即为答案。

    最小流

    先在没加附加边的网络上跑最大流，再对残量网络加入附加边 t→st \rightarrow s，最小流即为附加边的流量。

    例题

    经典问题

    二分图

    二分图最大匹配

    将源点连上左边所有点，右边所有点连上汇点，容量dou为 11。原来的每条边从左往右连边，容量也皆为 11，最大流即最大匹配。

    如果用 Dinic 算法求最大流，时间复杂度为 nm\sqrt{n}m。

    二分图最小点覆盖

    最小点覆盖：选最少的点，满足每条边至少有一个端点被选。

    König 定理：最小点覆盖 == 最大匹配。

    二分图最大独立集

    最大独立集：选最多的点，满足两两之间没有边相连。

    二分图中，最大独立集 =n −=n\ - 最小点覆盖。

    因为在最小点覆盖中，任意一条边都被至少选了一个顶点，所以对于其点集的补集，任意一条边都被至多选了一个顶点，所以不存在边连接两个点集中的点，且该点集最大。

    参考

    oiwiki

    路径覆盖与链覆盖

    DAG 最小路径覆盖

    DAG 最小路径覆盖：尽可能少的不相交的路径（链）覆盖掉所有节点。

    考虑把单个结点也看成一条路径，相邻结点合并路径条数就会减少，所以要最大化可以合并的个数。

    因为是最大化合并，考虑 二分图最大匹配 ，把每个点拆成 u′u' 和 u′′u''，原图上边 u→vu \rightarrow v 就在新图上连一条 u′→v′′u' \rightarrow v''，跑二分图最大匹配，就是最大的可合并的点数，总点数减去大的可合并的点数就是最小路径覆盖。

    DAG 最小链覆盖

    DAG 最小链覆盖：尽可能少的的路径（链）覆盖掉所有节点，可以相交。

    最小链覆盖与最小路径覆盖非常相近，考虑将最小链覆盖转化为最小路径覆盖。

    用 Floyd 求出原图的传递闭包，直接在传递闭包上跑最小路径覆盖即可。

    传递闭包：这里简单理解为对于所有联通的点对连边的新图

    DAG 最长反链

    反链：点的集合满足任意 x,yx,y，x,yx,y 互不连通

    Dilworth 定理：最小链覆盖大小 == 最长反链长度。

    最大权闭合子图

    闭合子图：对于点集 SS，任意 u∈Su\in S，uu 的出边的另一个点也属于 SS。

    最大权闭合子图：点权和最大的闭合子图。

    最大权闭合子图 == 正权和 −- 最小割

    例题

    P2762 太空飞行计划问题

    P3410 拍照

    最大密度子图

    最大密度子图：闭合子图使得 ∣E∣∣V∣\frac{|E|}{|V|} 最大。

    一般情况下，我们使用 01 分数规划 解决最大密度子图问题。

    二分比值 vv，建图

    • SS 到 ii 连容量为 mm 的边
    • ii 到 TT 连容量为 m+2∗v−degim+2*v-deg_i 的边
    • 原图上的边容量为 11

    如果流量 =n×m=n\times m 就存在密度为 ≥v\geq v 的子图。

    一般来说二分的 epseps 不能设太小，不然无法判断边是否有流量。

    例题

    UVA1389 Hard Life

    各种建模

    拆点

    本质上是将点的限制转化为边的限制。

    本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可