网络流及其简单建模

· · 算法·理论

0 前言

二月份的项目拖到现在。无语了。

中间因为很多问题中断了。当时觉得好多题目都不会，好难。现在回来看发现不少也挺简单的。

这篇文章总结了一些经典套路。如果有遗漏，请在文章末尾 pull request。 s 这篇文章不适合初学者学习网络流。因为讲的会比较简略，而且没有图。

不废话，马上开始。

1 前置内容

网络流问题是什么？

首先，网络流是一个在有向带权图上的问题。我们将每条边的“权”定义为“容量”，同时对于指定的两个点，将其设为“源点”和“汇点”。

具体的，如果将这个图抽象成一个输水系统，那么“点”就是水管交叉的地方，而“边”就是水管，而“容量”指的就是每条水管的最大输水量，“源点”就是自来水厂，“汇点”就是你家。

而一般的最大流问题指的就是，使自来水厂流到你家的水单位数量最大。

抽象的定义一下：

给定一个有向带权图 G = (V,E)，以下默认边 (u_i,v_i,w_i) 中 u_i 表示起点，v_i 表示终点，w_i 表示边权。

额外定义两个点 S,T。

对于每一条边，我们给出属性 f_i，满足如下条件：

最大化 \sum_{x = p \rightarrow T} f_x。

解决这个问题，我们可以想到朴素的贪心问题，即，每次找到一条 S 到 T 的路径，不难发现其对答案的贡献是路径上所有 f_i 的最小值，如果这个最小值 > 0 那么我们就加进贡献，然后把这条路径上的所有 f_i 都更新一遍，实际操作中，通常不记录 f_i，而是通过减小 w_i 来表示，我们称这条路径为增广路。

显然的，这么贪心做是错的。

不妨借用一点反悔贪心的思想，如果我们能够通过某种方式“撤销”贡献就好了，具体的，我们对于边 (u,v,w)。我们额外建一条 (v,u,0) 边，此时，如果我们将 (u,v) 减去一些贡献，那么就将 (v,u) 加上一点贡献，那么，此时增广路再经过 (v,u) 就意味着“撤销” (u,v) 的那点贡献。反过来也同理。这样，我们就实现了一条边的“选择自由”，而且我们剩下的就是只需要实现“寻找增广路”这一步骤了。

直接写深度优先搜索去寻找，即为 Ford-Fulkerson 算法，算法核心思想就是找增广路。

但是它的时间复杂度并不是多项式时间复杂度，具体的，为 O(mf)，其中 f 为最大流。这就意味着，在多数情况下，FF 算法并不适用。

接下来介绍 Dinic 算法。由于 DFS 先天的问题，可能会搜索到一个绕了路，比较差的增广路，那么为了解决这种问题，我们使用 BFS 进行分层。

具体的，每一次寻找增广路之前，我们先对原图做一次 BFS 分层，这样子可以有效避免出现绕路的情况。然后在这个基础上，我们再跑 DFS 求出增广路（只往层数比当前点多一层的方向增广），并修改路径。

我们还有一些优化：多路增广和当前弧优化。

多路增广指的是假设我已经找到了一条增广路，但是还有剩余的流量没有用，那么就继续寻找增广路，减少所消耗的时间。

当前弧优化指的是对于一个点，假设其被多次搜索到，我们可以从上一次搜索中断的地方开始搜，因为之前的那些边都是已经被增广过的，不可能会有剩余流量。

加上这两个优化，我们的 Dinic 时间复杂度就来到了 O(n^2m)。而且通常是跑不满的，一般来讲，如果确定一道题目是最大流，使用实现比较优美的 Dinic 是不会被卡常的。

还有一个很棒的常数优化，视使用情况可以加速 1.1 \sim 2.5 倍左右。如果被卡常了就可以用一用。就是在 BFS 的时候，如果搜索到了 T，那么就立刻退出。费用流感觉不太能用。

最大流大概就是这个样子。事实上，这个模型看上去使用范围很窄，但是经过合理的建图以及转化可以解决很多意想不到的问题，接下来这篇文章会介绍一些比较典型、简单且实用的模型。

例题请移步对应的网络流记录。

2 最大流模型

2.1 二分图最大匹配模型

首先先介绍一下二分图，或者说是二部图。字面意义上来讲，二分图就是分成两个部分的图，具体的，只有这两个部分之间存在边。抽象的说，对于两个部分 A,B，不存在 u \rightarrow v 使得 u,v \in A 或 u,v \in B。

而二分图最大匹配问题就是要让匹配数量最大。

对于这个问题，我们有匈牙利算法，匈牙利算法的核心思想是，尝试让对于一个点和一个目标点，尝试让匹配这个点的那个点 / 导致匹配的一些点进行重新匹配，如果可以重新匹配完成，那么就让这个点和目标点匹配。

但是这个问题也可以转化为最大流问题来解决，时间复杂度比匈牙利算法更优。

这就涉及到一个建模的问题了。事实上，网络流真正的难点并不是网络流本身，而是对于不同的问题，灵活构建网络流模型求解。

这是网络流中最简单的建模之一。具体的，我们不妨将 S 连向一类点，容量为 1，另一类点连向 T，容量同样为 1，原本的边全部定向为从 S 到 T 的容量为 1 的路径。

为什么这样做是对的？思考一下，对于一个匹配，我们占用了一条边和两个点，表现在网络流上就是流量变为了 1。

而给予一个点选择的权力，就相当于给它一个流量。

2.2 最大流等于最小割

首先我们要明白最小割的概念。如果仍然以上面的输水系统为例。那么最小割就是指将若干个水管割掉，割掉的代价是水管的容量，目标是让你的家和自来水厂不能通水，而且要让代价最小。

这其实就是一个最小割问题，解决方法也是比较简单的，就是根据以下结论：

最大流 = 最小割。

证明可以使用臆想法。

这个定理可以帮助解决更多的题目。现在看来这个结论还是比较显然的，但是之后会有非常多的应用。之后在解决最小割问题的时候，最好真的只是把它当作网络流，而不要想是怎么变成最大流的。这对于理解一些复杂的模型会有负面影响。

对于无向图最小割，显然一条边只会被割掉一次，因为一个割边一定出发方向是 S 集合，终点方向是 T 集合。那么两条边都割掉的话就违反了这个性质。

2.3 常用技巧：拆点与分层图

在很多网络流题目中，经常会看到题目有这样的限制：

限制这个点只能经过一次。

这个点的贡献只计算一次，重复经过不计算贡献。

同一天可能有多个状态的东西。如一天同时存在“干净”的毛巾和“脏”的毛巾。

或者给出更多奇怪的限制，比如说：

厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。

带有多个变量的限制，常规网络流的容量难以解决。

对于这种限制的解决方法，通常是拆点和分层图。

拆点，顾名思义，通常就是将一个点拆成多个点，借此来表示一些限制或者状态。直接说可能有点抽象，不妨来举一例来说明。

给定一个有向带权图。取其中一个点 x。现在我要限制经过这个点的流量为 [0,1]。

直接做显然并不好做，观察到，限制点是很难的，但是可以限制边。边是有容量限制的。

所以解决方法其实挺显然的了，就是把这个点拆成两个点，之间连接一条容量为 1 的边。

一般来讲，拆点就是为了满足一些奇怪的性质，或者额外记录一些信息。

有的时候，题目中可能会给定一些额外的限制或者数值，比如汽车的燃料数量，时间值等等，这些点可能会同时在一个点上处理。这种时候，不妨把数值不同的全部都拆开来，把图拆成多层，这也是所谓分层图的概念。

2.4 总量减去最小割模型

这是一个比较宽泛的概念，主要讲的是这么一件事：

答案 = 总量 - 最小割。

直接说还是很抽象。但是间接说也挺难的。

大概就是，当你同时出现代价和价值的时候，如果代价比较棘手，不妨转成最小割问题，割掉的边意思就是不选择这个点带来的贡献，或者是选择这个点但会产生代价。

那么这个时候跑最小割，最后答案就是所有的选择的贡献和，减去最小割的流量，也就是上面的那个式子。

结合太空飞行计划问题可以得到非常好的理解。

2.5 二者取一式模型

比较经典的模型了。

给你这么一个限制：

有若干个人做选择，选择 A 可以有 x_i 的贡献，选择 B 可以有 y_i 的贡献。

对于特定的若干对，同时选择 A 可以有额外的 a_i 的贡献，同时选择 B 可以有额外的 b_i 的贡献。

最大化贡献。

这种类型的题目相当多。发现这个其实是比较进阶的一个模型。具体的，我们先转答案为总量减去最小割。

不妨考虑一对“特定”的点对 i,j，其中先连边 S \rightarrow i,j 流量为选择 A 的代价，i,j \rightarrow T 为选择 B 的代价。如果没有额外的贡献这么做就是对的。

那么一起选择的时候，就是把同一对连接到 S 或者 T 的边割掉了。这个时候我们要让“额外的贡献”代表的边不被割掉。不妨额外建两个点 x,y 来处理同时选择造成的额外的贡献。此时满足同时选择且不被割去的一种简单易行的方式就是：S \rightarrow x，其流量为同时割 B 的贡献，然后 x \rightarrow i,j，并令流量为无限大（就是这两条边不能被割掉）

发现如果 i,j \rightarrow T 的边全部叉掉了，那么这条边是不用叉掉的。否则这条边肯定要被叉掉。

对于同时割 A 的贡献也这么做就可以了。

2.6 方格图上的建模技巧

好像讲的有点迟。

某句至理名言宣称：“网格图有一半都是网络流。”由此可见方格图与网络流结合的有多紧密。无论是常规的建图，还是平面转对偶，还是黑白染色都跟方格图有关系。

首先是黑白染色这一重要技巧。当出现相邻有关的限制的时候，有相当大的概率是要往黑白染色这一个角度去想的。具体的，我们类似于国际象棋棋盘一样对每个格子做黑白染色。对黑色格子做一种处理，对白色格子做一种处理。这样就可以方便的处理相邻这一限制条件。这一个也可以跟上面提到的二者取一式结合在一起。

然后是平面转对偶。这个其实用的不多。也不一定限制在网格图上面。但是出现对边做一些处理的时候（比如割掉网格图上的某个边），不妨考虑使用平面转对偶做处理。

当然，有的时候涉及到一些路径问题，这种时候，直接在原图上面建图可能也会比较方便。

2.7 路径覆盖问题模型

路径覆盖问题看似与网络流问题没有任何关系。

但事实上还是有相当多的用处的。路径覆盖问题是为了解决下面这样的问题：

给定一个 DAG，求最少需要多少条路径，使得这些路径经过所有点恰好一次。

一条路径可以只有一个点。

首先发现这么一个很聪明的想法：首先令每个点自身都为一条路径。这样一开始一共就有 n 条路径。

现在定义一个 merge 操作，就是把两条能够相连的路径合并到一起。那么我们的目标就是要让合并的数量尽量多。

好，依照这个，我们来开始建模。首先我们注意到，两条路径合并必须满足一条路径的尾部通过一条边接到了另一条边的头部。

所以我们拆点建二分图，对于每个点用 x 表示这个点的尾部，x' 表示这个点的头部。显然一个点只能有一个头部和一个尾部，所以源点汇点各自连容量为 1 的边。接下来，对于原来在图上的边 (i,j) 我们连接 i \rightarrow j' 这条边。发现只要流过这条边，就相当于用掉了一个点的头部和尾部，就相当于一次合并。

又知道合并一次就是使得边的数量减 1。所以最后最小路径条数就是 n 减去最大流。

2.8 切糕模型

比较厉害的模型。来自于省选题目 [HNOI2013] 切糕。

相关内容可以找到之前写过的这道题的题解。这里不再赘述。

3 费用流

接下来讲讲费用流。

费用流与网络流的模型基本类似，只是边多了一个费用的限制。

如果仍然是以上面的输水系统为例子，那么这次每个管道都开始收取过路费了，流过多少流量就要收成正比的费用。

一般来讲是求解最小费用最大流问题。

具体流程来讲，首先是套用之前的 Dinic 可以来做这个问题。具体的，我们把分层图使用 bfs 的过程改成用 SPFA。至于反向边这种都是随便做。时间复杂度难以计算，但是自己试一试就跑的挺快的。

可能更快的是 zkw 费用流。但是实现方式和 Dinic 的方法有不少区别，而且看到卡 Dinic 的比较少，所以这里不再描述。（其实就是不会）

对于最大费用最大流问题，直接把费用取反，然后又变成了最小费用最大流问题，最后要对答案取一个反。

费用流的套路基本上跟网络流是那么一个回事。在处理限制比较多的时候（比如说，有一个数量的限制，但是又有一个花费，让你算最小花费之类的），或者限制和要求的东西不一样的时候，加入费用这一概念通常能够很好的解决问题。

对于有负圈的费用流，参见下一节。

4 上下界网络流

这个会比较 complicated。

首先我们要知道，上下界网络流就是，边现在有了一个流量下界。就是一条边一定要流过这么多流量，不能少。那么问题一般也就比较多元化了，有可能是有源点汇点的，也有可能是没有的。有可能是求可行流，有可能是最大流，甚至有费用可行流等等。以下一个个来阐述。

4.1 无源汇上下界可行流

限制已经用标题描述的很清楚了。这个是最简单的一种。

首先我们把图拆成“下界网络”和“差网络”。

下界网络就是边权只有下界的网络，差网络就是边权为上界减去下界的网络。

如果是可行流，那么我们只需要判断 Yes 还是 No。所以直观的我们不用管流量的大小，我们只需要尝试让下界网络和差网络的和为原图的一个可行流即可。

先从下界网络入手。首先我们肯定希望下界网络是满流的啊！要不然我们是达不到限制的。所以我们先给所有边给搞到满权。但是，满流不意味着流量平衡，有些点可能流入的流量比流出的流量要多，等等。但是我们又要强制下界网络满流，所以接下来，我们在差网络上面动手脚。

假设我在下界网络中，这个点净流入了 x 点流量，那么我当然希望在差网络里面，这个点能够净流出 x 点流量，只需要我们从虚空中掏出 x 点流量就好了。反过来道理也是一样的，只要我们把那些流量塞回虚空即可。

所以我们还是屈服于虚空，建立一个源点和汇点，按照上面说的方法连接附加边，给每个点补充流量或者拿走流量，然后跑一个简简单单的网络最大流。平衡的条件就是所有的附加边都流满了。这个记录一下和，判断最大流等不等于这个和就行，显然流出的附加边和流进的附加边容量是一样的。虚空什么也没有失去，但你屈服于衪。

扯远了，说回来，其实你不需要建出下界网络，你只要直接判断是不是流量平衡，然后直接在差网络上操作即可。

4.2 有源汇上下界可行流

观察到，有源汇的区别就是现在源点和汇点不流量平衡了。

怎么不平衡的呢？就是 S 会失去一定的流量，而 T 会得到相同数量的流量。那把这个补充回来就好了！我们从 T 向 S 连边，由于流量从 0 到 +\infty 都有可能，所以边权是 [0, +\infty)。然后接着按照无源汇的去做即可。

注意到这里的源点和汇点已经被处理成普通点了，所以也是要连接附加边的。实际上一般处理 +\infty 其实只是一个很大的值，所以是可以这么做的。

4.3 有源汇上下界最大流

那么这个问题就是比较实际的问题了。

回退到上一节，我们已经得到了一个可行流，那么现在是压榨时间！我们先把所有的附加边和附加边用的那对源点和汇点删掉，然后再把原图中的那对源点和汇点之间的边给删掉。那么剩下一个普普通通的网络流图。发现我们现在在这个图上面跑最大流不会超越上界或者下界，或者导致流量不平衡（已经平衡过了），所以从源点到汇点跑一遍普普通通的最大流即可，把剩余流量全部压榨干净。

其实那些附加边不用删的，流量全都是 0，进不去，怎么想也进不去吧。

最小流怎么做？只要从汇点到源点做最大流即可！这样剩余流量反而变成了那些多流的边。然后只要把一开始得到的流量减去我们这么做得到的最大流即可。

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

一个道理吧。我们只要把差网络搞完之后做的最大流改成 MCMF 即可，最后答案别忘记加上下界网络造成的流量。

注意不是这个不保证流最大的前提费用最小，我们只是让费用最小。

最大流最小费用类比普通可行流类推到最大流，我们也在跑完的网络上面再跑一遍 MCMF 即可。

5 后记

就这样吧。网络流怎么能是写的明白的。自己做题才能最明白。

我的二十四题笔记：https://www.luogu.com.cn/article/7rk153pi

我的其他网络流题笔记：https://www.luogu.com.cn/article/f05t3qzh