上下界网络流 & 上下界费用流

Author Avatar
dozbear 4月 30, 2017
  • 在其它设备中阅读本文章

准备工作

  • 你需要了解什么是网络流
  • 你需要掌握一些高效率的网络流算法,通常为 dinic 或者 isap

在这篇文章中, 表示在 之间连接一条容量为 的边,有时 后增加一个参数 代表费用

所有求上下界最大流都包含求可行流的过程

网络流是什么?

在图论中,网络流(英语:Network flow)是指在一个每条边都有容量(capacity)的有向图分配流,使一条边的流量不会超过它的容量。通常在运筹学中,有向图称为网络。顶点称为节点(node)而边称为弧(arc)。一道流必须匹配一个结点的进出的流量相同的限制,除非这是一个源点(source)──有较多向外的流,或是一个汇点(sink)──有较多向内的流。一个网络可以用来模拟道路系统的交通量、管中的液体、电路中的电流或类似一些东西在一个结点的网络中游动的任何事物。

这段很弱智啊,为什么要加上呢?

因为博客的首页预览写的有问题,写的公式在预览里面直接就被 mathjax 渲染了,每个博客厚度不一样非常丑(逃

为了说明网络流本质是节点 流入=流出 ,思考时比把它想成类似水管什么的管用一点

无源汇上下界可行流

对于每个节点记录流量平衡

对于每一条边 ,存在上界 和下界

最后,如果

大力网络流一遍,如果 的出边都跑满就有可行流

无源汇上下界最大流

最大流是不存在的辣,连源和汇都没有没有东西可以最大化

事实上跑在网络里面的东西只是很多环串起来,随便动一动流就不一样了

有源汇上下界最大流

连一条上界为 下界为 的边就变成无源汇的情况啦,先求出可行流

然后再在残余网络上求 的最大流,再把两次最大流的答案加起来

有源汇上下界最小流

可以二分,添加一个超级超级源

也可以先不连 的那条边,然后按照无源汇上下界最大流的方法建图,先从超级源到超级汇跑一遍最大流,再加上 的那条边,在残余网络上再跑一次最大流,第二次最大流就是答案

为什么要先从 跑一遍呢?尽可能利用原图中的环啊

这样先跑一下环里面的100就没有了

(这张图好像是SJTU的课件里面的

为什么这样做呢?

感性的来理解,第一步中求最大流,所有能流的边都“竭尽全力”的流完了;
第二步再求最大流的时候,汇到源上的流量就会尽可能的小(即源到汇的流量尽可能小)

无源汇最小费用流

消负圈

还是再说一遍循环时是不存在最大流的

拒绝负圈?

一个小技巧

对于每个点 ,拆点 ,然后

同时对于每个 ,拆成

然后跑 最大费用最小流

为什么呢?这样可以强制每个节点流量平衡

因为在计算机里无限是一个很大的数而不是一个真的无限

就这样啦

无源汇上下界最小费用流

对于每一条边 ,存在上界 和下界 ,费用为

然后从超级源到超级汇跑一边,如果 出边都满流了跑出来的 就是答案啦(为啥呢?最小费用流啊

有源汇上下界最小费用流

感觉玩法很多啊

可以把有上下界要求的边大力拆一拆,然后把 的那一部分的费用加上 ,最后算出答案时再减掉(纯yy,这种做法应该要先判一下可行还可能要消负圈

或者……(当然也是最简单的办法

先加一条 流量为 费用为 的边,然后跑无源汇上下界最小费用流

其实从流量平衡的角度重新看无源汇上下界可行流,发现其实记录的 本质上每次每条有限制的边都以费用流的这种方法连一边,然后把很多直接从源到点到汇的边消掉了

例题

回头补吧,一时半会儿翻不出来

本作品采用 CC BY-NC-SA 4.0 Unported 进行许可
本文链接:https://dozbear.com/bounded-network-flow-review/