上下界网络流及费用流学习笔记

前言

---

无源汇上下界可行流：

模型：一个网络，求出一个流，使得每条边的流量必须且，每个点必须满足总流入量 = 总流出量 (流量守恒) (这个流的特点是循环往复,无始无终)

考虑到如果存在一个可行流，那么每条边的流量至少是 ，于是我们可以预先让它先流

这样以后一个点流入量可能就不为流出量了

我们考虑求出一个附加流，每条边的最终流量为附加流流量加上

具体而言，我们建边建成

考虑到最后要让流量平衡，分类讨论：
如果一个点的初始流入 = 流出那么它平衡了
如果初始流入 > 流出，那么这个点在附加流中流入 < 流出，称为 类点
如果初始流入 < 流出，那么附加流流入 > 流出，称为 类点
记差量为

为了使流量平衡，我们建立超级源汇 ， 向 类点连边，流量为
类点向 连边，流量为

容易发现，与源点汇点向连的边边权和是相等的
有解当且仅当把不平衡的流量填平，也就是 的所有出边入边满流

跑一个 到 的最大流即可

---

有源汇上下界可行流

源点和汇点的流量始终不会平衡

考虑到源点出去的流量 = 汇点进的流量，汇点向源点连流量 的边就可以平衡

整个可行流的流量就是汇点到源点那条边的流量

---

有源汇有上下界最大流

在满足可行即流量平衡的条件下流量最大

建图如上，我们发现残余网络中有些边是没有跑满的

把与超级源汇的边断开，然后在残余网络上跑一个原图 的最大流

最终的最大流需要加上原本的可行流

最小流可以倒过来跑， 到

---

无源汇上下界最小费用可行流

同样建立超级源汇

对于边 ，建边 ，并将初始值加上

对于那些流量不平衡的点，建边同 “ 无源汇上下界可行流 ”，费用为 0

然后跑 到 的最小费用最大流

有源汇加一条原图中