上下界网络流笔记

Author Avatar
WildRage 1月 16, 2018
  • 在其它设备中阅读本文章

无源汇可行流

将上下界的网络流转化为普通网络流。

建图:

  • 添加源点 $S$ 与汇点 $T$
  • 对于原图中的边 $a \to b$ 流量限制为$[c, d]$, 则连边 $a \to b$, 流量为 $d-c$
  • 对于原图中的每一个点 $i$ , 记 $d(i)$ 为流入这个点的所有边的下界 $-$ 流出这个点的所有边的下界
    • 若$d(i) > 0$连 $S \to i$, 流量为 $d(i)$
    • 若$d(i) < 0$连 $i \to T$, 流量为 $-d(i)$

在新图上跑 $S \to T$ 的最大流
若新图满流则原图存在可行流
原图中边流量为新图中对应边的流量加下界。

有源汇可行流

建图:

  • 在原图中加一条 $t \to s$ 的边流量为 $[0, INF]$
  • 用无源汇求解

有源汇最大流

建图 同上

在新图上跑 $S \to T$ 最大流
记此时 $\sum{f(s, i)} = sum1$
讲 $t \to s$ 的边拆掉, 跑 $s \to t$ 的最大流
记此时 $\sum{f(s, i)} = sum2$
则答案为 $sum1+sum2$

有源汇最小流

建图方法同无源汇可行流
求 $S \to T$ 最大流
连边 $t \to s,INF$
求 $S \to T$ 最大流
答案为 $t \to s$ 的实际流量

有源汇费用流

将上下界的网络流转化为普通网络流。

建图:

  • 添加源点 $S$ 与汇点 $T$
  • 对于原图中的边 $a \to b$ 流量限制为 $[c, d]$, 费用为 $v$ , 则连边 $a \to b$ , 流量为 $d-c$ , 费用为 $v$
  • 对于原图中的每一个点 $i$, 记 $d(i)$ 为流入这个点的所有边的下界 $-$ 流出这个点的所有边的下界
    • 若$d(i) > 0$连 $S \to i$, 流量为 $d(i)$, 费用为 $0$
    • 若$d(i) < 0$连 $i \to T$, 流量为 $-d(i)$, 费用为 $0$

连边 $t \to s$,流量为 $INF$,费用为 $0$

跑 $S \to T$ 的最小费用最大流
答案为 $ans+$原图中边的下界$\times$边的费用

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接:https://blog.wildrage.xyz/2018/01/15/122/