手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

环球聚焦：算法学习笔记(8.2): 上下界网络流

2023-01-14 21:57:41 来源：博客园

上下界网络流

上下界网络流
- 无源汇可行流
- 有源汇上下界可行流
- 有源汇上下界最大流
- 有源汇上下界最小流
- 作者有话说

前置知识以及更多芝士参考下述链接网络流合集链接：网络流

上下界网络流是普通网络流的一种变体，对于网络流，我们不仅关注其流量的上界，下届同样有所体现。题型大致有五种

【资料图】

有源汇
无源汇
可行流
最大流
最小流

虽然听着挺唬人的……其实理解了也非常简单

无源汇可行流

这是上下界网络流的基础，也是最简单的一种

给定一个没有源点和汇点，每条边有上下界的流量网络，目的是求有没有一种可能的流使得流量守恒

流量守恒：每一个点流入和流出的量相等

考虑这样一个图

我们先画出两个图

稍后解释是什么，以及有什么用

下界网络：

以及差界网络：

我们根据原图原图结构构造出了两张图

下界网络每一条边对应着流量下界，差界网络的每一条边容量对应着原图流量上下界的差

我们希望两个网络流相加之后恰好是原图的一种可行流，这首先要求下界网络是满流的（可行流至少必须达到下界）

但是考虑到流量守恒，我们需要对下界网络上不平衡的结点在差界网络上进行处理

首先我们在下界网络中新建一个虚拟源点 \(S"\) 和虚拟汇点 \(T"\)

本文中虚拟的点都以 \("\) 结尾

接着考虑在下界网络中的一个点 \(x\), 我们假设其流入流量为 \(in(x)\), 流出流量为 \(out(x)\)

那么一共会出现三种情况：

\(in(x) \gt out(x)\) 即流入大于流出。那么在差界网络中，我们需要补齐多流入的部分。那么我们通过虚拟源点向点 \(x\) 连一条容量为 \(in(x) - out(x)\) 的边。
\(in(x) = out(x)\) 即流入等于流出，此时不需要处理
\(in(x) \lt out(x)\) 即流入小于流出，那么在差界网络中，我们需要补齐多流出的部分，所以，\(x\) 向虚拟汇点连一条容量为 \(out(x) - in(x)\) 边

通过上述处理之后，差界图就变为了：

左图为处理过的差界网络，右图为下界网络

在保证了下界网络的流量守恒之后，我们在修改过的差界网络上从 \(S"\) 到 \(T"\) 跑一次最大流，把每一条在原图上的边的流量加回到下界网络中，就是获得了一种可行流。

但是，总归是有不可行的时候：如果我们新建的附加边没有达到满流状态，表明在差网络没有办法补齐下界网络中的不守恒，也就是说，原网络中不存在可行流。

在实际中，我们并不需要建立下界网络，只需要对于查网络进行处理即可
在最后判断的时候只需要判断所有关于源点的附加边是否满流，或者所有关于汇点的附加边即可

有源汇上下界可行流

思考一下，在有源汇的网络流中，流是如何”流动“的

很明显，是从源点到汇点

也就是说，源点吐出流量，汇点吃到流量，且源点吐出和汇点吃掉的流量一定一是一样的

那么考虑我们如何将流量恒定的留在网络中？

很明显，我们把汇点吃掉的流量流回源点即可

换句话来说，我们只需要在实际汇点 \(T\) 到源点 \(S\) 连接一条流量为 \(INF\) 的边就行了

如此处理之后，我们就把源点和汇点处理成网络中的一般点了

接着我们就只需要把它与一般的无源汇图进行一样的处理即可

如何寻找可行流流量？
由于我们将源点的流量流回了汇点，所以实际流量就是我们新建的从汇点到源点的边上的流量

处理之后大致是这样的

有源汇上下界最大流

考虑我们在处理后的图中得到了一个可行流，但是从实际源点与实际汇点间还可能有额外的流量

注意一下，下面是在跑完第一次最大流的剩余网络的基础上进行操作
最小流亦是

所以我们把在差界网络新建的所有额外边的流量设为 \(0\)（相当于删除这些边）然后再从 \(S\) 到 \(T\) 跑一次最大流即可

形象一点，我们在跑 \(S"\) 到 \(T"\) 的最大流时并不一定榨干了 \(S\) 到 \(T\) 的剩余流量，所以还需要再榨一次 \gou

那么此时原网络的最大流即是两次跑最大流的流量和

模板题：Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流 - 洛谷
NOTICE:在这种稠密图上跑最大流，还是必要当前弧优化的，不然会死的很惨……

有源汇上下界最小流

与最大流类似，但是不是榨干了，是把榨了的还回去 ~~有种心虚的感觉~~

所以，同样处理所有新建的额外边，但是这次是从 \(T\) 到 \(S\) 跑一次最大流

可以看作把流量流回去

此时原网络的最小流即是两次最大流的流量差

作者有话说

如果我们在求最大或者最小流的时候采用的是ISAP算法，那么千万要记住，在删除边之后需要更改源点汇点重新跑一次BFS更新深度（其实不更新也没大问题，反正错了也不给钱是吧 ^_）

关键词：我们需要也就是说