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

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

准备工作

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

在这篇文章中,\( addedge(u,\ v,\ cap) \) 表示在 \(u\) 和 \(v\) 之间连接一条容量为 \(cap\) 的边,有时 \(cap\) 后增加一个参数 \(cost\) 代表费用

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

网络流是什么?

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

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

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

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

无源汇上下界可行流

对于每个节点记录流量平衡 \(bal_u\)

对于每一条边 \(e_{uv}\) ,存在上界 \(max_{uv}\) 和下界 \(min_{uv}\)

\[ addedge(u,\ v,\ max_{uv} - min_{uv})\]

\[ bal_u-=min_{uv} \]

\[ bal_v+=min_{uv} \]

最后,如果 \(bal_u>0\) 就 \(addedge(S,\ u,\ bal_u)\)

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

无源汇上下界最大流

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

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

有源汇上下界最大流

从 \(T\) 到 \(S\) 连一条上界为 \(\infty\) 下界为 \(0\) 的边就变成无源汇的情况啦,先求出可行流

然后再在残余网络上求 \(S\) 到 \(T\) 的最大流,再把两次最大流的答案加起来

有源汇上下界最小流

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

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

为什么要先从 \(S\) 到 \(T\) 跑一遍呢?尽可能利用原图中的环啊

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

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

为什么这样做呢?

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

无源汇最小费用流

消负圈

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

不想写消负圈?

小trick

对于每个点 \(u\),拆点 \(u_1\) 和 \(u_2\),同时

\[ addedge(S,\ u_1,\ \infty)\]

\[ addedge(u_1,\ u_2,\ \infty)\]

\[ addedge(u_2,\ T,\ \infty)\]

同时对于每个 \(addedge(u,\ v,\ cap)\),拆成 \(addedge(u_1,\ v_2,\ cap)\)

费用流就不说了一个道理,加上费用而已

无源汇上下界最小费用流

对于每一条边 \(e_{uv}\) ,存在上界 \(max_{uv}\) 和下界 \(min_{uv}\),费用为 \(cost_{uv}\)

\[ addedge(u,\ v,\ max_{uv} - min_{uv},\ cost_{uv}) \]

\[ addedge(S^{super},\ v,\ min_{uv},\ cost_{uv}) \]

\[ addedge(u,\ T^{super},\ min_{uv},\ 0) \]

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

有源汇上下界最小费用流

感觉玩法很多啊

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

或者 …

先加一条 \(T\) 到 \(S\) 流量为 \(\infty\) 费用为 \(0\) 的边,然后跑无源汇上下界最小费用流

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

例题

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