上下界网络流笔记

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

无源汇可行流

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

建图:

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

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

有源汇可行流

建图:

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

有源汇最大流

建图 同上

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

有源汇最小流

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

有源汇费用流

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

建图:

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

连边$t->s$,流量为$INF$,费用为$0$

跑$S->T$的最小费用最大流
答案为$ans$+原图中边的下界*边的费用

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