上下界网络流学习笔记

2021/1/23 upd: 复习的时候回来看，然后就开始改改改……修了各种锅，加了点没用的东西。

2021/7/7 upd: 修正表达。

其实这篇东西的内容与参考的博客写的差不多，只是加上了个人的理解与几个图。

在学习之前先来看一道例题。

集训队互测2013 供电网络

给出一个流网络，对于一条流量为 的边费用为 ，每一条边 有一个最小流量 和最大流量 ，每一个点初始有一定流量 （可能为负），同时每一个点可以花 费用补充流量、 减少流量，求使每个点流量为 0 且每条边的流量满足的上下界的最小费用。

首先来看题，我们发现里面充满着网络流基操：建源汇、拆费用边、最小流量……

非常完美的网络流 N 合一板子题。

然我并不会上下界……

无源汇上下界可行流

首先我们注意到“无源汇”，这说明这玩意并没有源点或汇点。

那么流量从哪来？

既然没有源节点 生产者 和汇结点 消费者 ，流量当然是凭空产生的啦！虽然听起来非常草率，但这个玩意确实是这么定义的，只要满足流量守恒就可以了。其效果约等于一堆流量在流网络里不断转圈。

那么我们不产生可不可以

现在的问题在于，对于一个有下界的边，它必须要流其下界的流量，这令人感觉非常不好处理。

优先增广没到下界的边

于是反过来想，对于某条边，反正都要流这么多流了，那么不如直接让它流这么多流，起点一定是要少这么多流量的，而终点也一定是要多这么多流量的。于是我们新建一个超源，往这条边的终点建一条下界容量的边，表示这个点一定会有这么多流量。具体怎么来的并不重要，反正不管是偷的抢的捡的就有这么多了；同时这条边的起点向超汇连一条下界容量边，表示这个点必须要有这么多流量。

现在剩下一个问题：多/少的流量怎么办？

当然是使用剩下的边的容量流过去啦！

于是直接从超源到超汇跑一边最大流，如果每一个点的请求都能被满足（每一条从超源发出的边都满流），那么这个流网络就是有可行流的。

当然，实际处理时一般是先把所有边的两边直接加减处理之后再加边的，如果某个点为正数，就表示它多了流量，要从源点接过来并经由别的某些点送到汇点去。如果为负，表示它要从别的点那里领流量并补到汇点去。

讲的有点多，不如上一张图：

1
2
3
4
graph LR 
    1((1)) --3/5--> 2((2))
    2((2)) --3/4--> 3((3))
    3((3)) --1/3--> 1((1))

现在有这样一个上下界流网络，我们一眼可以看出一个可行流是每条边3流量。

现在要对这个图进行一些处理：

对于结点1，流入1流量，流出3流量，所以往 TT 连出一条容量为2的边。

对于结点2，流入3流量，流出3流量，所以不与 SS 或 TT 连边。

对于结点3，流入3流量，流出1流量，所以从 SS 连入一条容量为2的边。

然后对于原图中的边，显然上界减去下界还剩下一些容量，所以还要连起来。

所以图长这样：

1
2
3
4
5
6
graph LR
    0((SS)) --2--> 3((3))
    1((1)) --2--> 2((2))
    2((2)) --1--> 3((3))
    3((3)) --2--> 1((1))
    1((1)) --2--> 4((TT))

经过一波构造，我们偷税的发现，令人烦躁的流下界全都去吃梁非凡套餐了。

然后跑一边最大流，发现从 SS 连出的边全部满流了，于是说明这玩意有一个可行流。

Q：为什么不检查 TT 跑满没有？

A：因为显然 SS 连出的容量和 TT 连入的容量是一样的。 好像这个制杖问题只有我会问

如果要输出方案直接输出原图中的边的流量即可，如果要费用流也显然可以直接套上去。

然后我们发现这并不能解决一开始的问题，因为我们在建图时会有一对源汇。

有源汇上下界网络流

可行流

上面已经说了，无源汇上下界可行流的效果约等于一堆流量在流网络里不断转圈。但这里我们有一个源汇，这俩家伙显然不满足流量守恒，也就是流量在流网络里并不能乱跑，所以就不能直接凭空产生流量。

那么我们从汇点向源点连一条上界无穷下界为0的边，就可以让到了汇点的流量再回到源点，这样就可以让源点与汇点也满足流量守恒。

让流量获得解放，让它们自由的飞翔

于是我们就把有源汇转换成了无源汇，因为网络流中源汇点的作用就是它们不满足流量守恒 生产者与消费者 。而这里我们让这两个家伙满足了流量守恒，于是这俩家伙就被架空了，失去了不满足流量守恒的权力与普通点无异，我们就可以再建一个真正的超源汇来搞定上下界了。

注意： 因为现在的假源汇点跟普通点是一样的，所以不要因为它们曾经的地位就忘了让超源汇向它们连边了。

稍微弄一幅图示意一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
graph LR
    subgraph 新图
        SS((SS)) --1--> 12((1))
        SS((SS)) --1--> 22((2))
        SS((SS)) --2--> T2((T))
        T2((T)) --inf--> S2((S))
        S2((S)) --2--> 12((1))
        S2((S)) --1--> 22((2))
        12((1)) --2--> 22((2))
        22((2)) --3--> T2((T))
        S2((S)) --4--> TT((TT))
    end
    subgraph 原图
        S((S)) --3/5--> 1((1))
        S((S)) --1/2--> 2((2))
        1((1)) --2/4--> 2((2))
        2((2)) --2/5--> T((T))
    end

我们发现 SS 连出来的边是能跑满的，于是原图有一个可行流。

题解

到这里我们就可以解决开头的那道题了，我们先让假源到每个点那里兜售流量，再让假汇到每个点那里低价回收流量 低到负价 ，这样看起来我们把源点直接连无穷边连到了汇点，不过因为这两家伙是假的，所以并不影响正确性。接下来再把每条边拆费用，然后按刚刚的方法搞有源汇上下界可行流板子即可，记得用费用流。 废话

最大流

注意到这个被丢进有源汇里了，因为如果没有源汇的话你还打算统计在流网络里有多少流量在转圈不成……

关于这玩意为什么不能是无源汇的可以非常简单快速不要脑子的用反正法证明：“反正也不考。”

首先先按可行流的方法跑一边，然后现在就是要榨干剩下的边的流量。

那么我们把从 T 到 S 的无穷边删掉（如果不删掉就会把这条边上加载的流量从反向边上全推回去， SS 和 TT 的边可以不删因为不会联通 S 和 T ），从 S 到 T 跑一遍最大流，再加上原来的可行流即可。

最小流

其实跟上下界最大流差不多，只不过做完可行流之后我们的任务变成把尽可能多的流量推回去。

于是我们照样的把从 T 到 S 的无穷边删掉（如果不删掉就会把无穷的流量直接推到源点去，然后就 GG 了），然后从 T 到 S 跑一遍最大流（直接在残量网络上跑，不需要建反向图什么乱七八糟的东西），从可行流上减掉即可。

费用流

把预加载的流量的费用算出来，然后正常跑费用流。

显然 SS 和 TT 的边是没有费用的。

这一段水极了

习题

先是模板题：无源汇可行流 、 有源汇最大流 、 有源汇最小流 。

ZOJ3229. Shoot the Bullet （有源汇最大流）

BZOJ3698. XW的难题 （有源汇最大流）

BZOJ2502. 清理雪道 （有源汇最小流）

SNOI2019 通信 （费用流 ，可以不用上下界）

BJWC2018 Kakuro （费用流 ，可以不用上下界）

这里的 BZOJ 链接指向某个离线题库。 要交的话就不用科普去哪了吧

题解什么的咕咕咕。 才不是因为没做

不幸的是开头那道题并没有哪个公开OJ收录（至少本蒟蒻没找着），只能在某个校内OJ交。

更不幸的是这玩意好像真的没人考以至于我找不到什么题（捂脸）……

参考博客

https://blog.csdn.net/corsica6/article/details/81488993

https://blog.csdn.net/Clove_unique/article/details/54884437

https://blog.csdn.net/HiChocolate/article/details/85239805

≡