本文同步发布于 博客园@QWQcoding 洛谷博客@QWQcoding

基础知识

网络流简介

网络流是一个定义在图上的概念。它定义在一个带权无向图上，其中权值被称为容量，表示这条边能够承受的最大流量大小。然后拥有两个特殊的节点：源点与汇点，表示你需要设计一种把流量从源点 \(s\) 运送到汇点 \(t\) 的方案，使得每条边的流量都不超过其容量大小。

性质：源点没有入边，汇点没有出边，除了这两个点之外的所有点必须满足流出的流量之和与流入的流量之和相等。

最大流：在满足网络流要求的情况下从源点流到汇点的最大流量大小。记为 \(f(s,t)\) 。

残量网络：图中剩下的容量组成的新图。

下面 \((u,v,c)\) 表示一条从 \(u\) 到 \(v\) ，容量为 \(c\) 的边

最大流

EK算法

EK算法：每次对一张网络流图，每次在残量网络中找到一条流量不为 \(0\) 的路径，对其进行增广。

复杂度：\(O(VE^2)\)

由于其效率过于低下，在OI中几乎用不到。

Dinic算法及当前弧优化

在EK算法基础上进行了改进，优化了寻找路径的方式，同时每次对多条路径增广。

具体来说：Dinic算法每次增广前会先跑一遍bfs，对残量网络按到 \(S\) 距离分层，只寻找满足 \(d_v=d_u+1\) 的路径。

同时我们每次不再只增广一条路，而是对所有满足条件的路径同时增广。

当前弧优化：在每次增广时对每个点维护一个指针，它指向最靠前的满足增广条件的边 \((d_v=d_u+1\) 且 \(cap_{u,v}>0 )\)

复杂度：\(O(mn^2)\) 。

同时在二分图上复杂度变为 \(O(m\sqrt n)\) 。

由于Dinic好写，并且速度较快，于是它是OI中最常使用的最大流算法。

最高标号预流推进算法(HLPP)

复杂度有保证，为 \(O(n^2\sqrt m)\) 。但由于一般题目中建出来的图都有特殊性质，经常打不过Dinic。

OI-wiki: HLPP。

最小割

对于一个图 \(G=(V,E)\) ，它的一个割定义为一种把 \(V\) 划分为两个集合 \(S,T\) 的方式，使得 \(s\in S,t\in T\) 。

割的容量 \(cap(S,T)\) 定义为 \(\sum_{u\in S,v\in T,(u,v)\in E} cap(u,v)\) 。意思就是需要断掉的边的容量之和，使得 \(S\) 的点不能到达 \(T\) 的点。

最小割就是使得 \(cap(S,T)\) 最小的一种划分方式。

最小割最大流定理

利用对偶原理可以得出最小割和最大流相等。

可以感性理解一下。

大概就是最小割限制了最大流的大小，而最大流又给出了一种可行的最小割，于是两者就相等了。

求最小割的方案

先跑一遍Dinic，然后从 \(s\) 开始bfs，沿着 \(c>0\) 的边走，能到的点全部划到 \(S\) ，剩下的划到 \(T\) 。

大致证明：在跑完最大流后残量网络不连通，于是按照残量网络的连通块划分。而对于任意一个点集 \(V\) 都会满足其流入量之和等于流出量之和。于是 \(S\) 的流出量之和就是 \(f(s,t)\) 。于是此时被删掉的边容量之和就是 \(f(s,t)=c(s,t)\) 。

最大权闭合子图

给定一个有向图，点有点权。如果一个点 \(u\) 被选了，所有 \(u\) 的出边指向的点 \(v\) 也必须选。求最大收益。（点权可以为负数）

利用最小割来解决。先假设所有正点权都选。正点权连到 \(S\) ，表示放弃这个点，负点权连到 \(T\) ，表示选择这个点。原图中所有 \((u,v)\) 连接一条 \((u,v,\infin)\) 的边。

上下界循环流

循环流：没有源汇网络流。

上下界循环流：在网络流基础上，每条边多给一个下界，表示至少流这么多。

先强制每条边流下界这么多。建立超级源汇点 \(S,T\) ，令 \(d_u\) 为 \(u\) 的流出量-流入量，如果 \(d_u<0\) ，那么连 \((S,u,d_u)\) ，否则 \(d_u>0\) 连 \((u,T,−d_u)\) 。

最后跑一边最大流，检查一下是否满流。

正确性：这种做法保证了流量平衡，并且如果有解一定可以按如上方式构造。

上下界最大流

给定源点汇点 \(s, t\) ，求上下界最大流。

连接 \((t,s,\infin)\) ，先跑一遍上下界循环流。然后再把 \((t,s)\) 边断掉，再跑一遍 \(s\) 到 \(t\) 的最大流。

大致证明：首先我们求出了一组合法的流，然后在这组流的基础上增广。容易发现一定可以增广出最大流。

上下界最小流

给定源点汇点 \(s,t\) ，求上下界最大流。

连接 \((t,s,\infin)\) ，先跑一遍上下界循环流。然后再把 \((t,s)\) 边断掉，再跑一遍 \(t\) 到 \(s\) 的最大流。

大致证明：首先我们求出了一组合法的流，然后在这组流的基础上退流。容易发现一定可以退出最小流。

最小费用最大流简介

最小费用最大流（简称费用流）定义类似网络流，每条边多了一个费用，要求在求出最大流的基础上满足费用最小。下面 \((u,v,c,w)\) 表示一条从 \(u\) 到 \(v\)，容量为 \(c\) ，费用为 \(w\) 的边。

SSP算法

SSP算法：每次对一张网络流图，每次在残量网络中找到一条流量不为 \(0\) 的最短路径，对其进行增广。

如果图上存在单位费用为负的圈，SSP算法正确无法求出该网络的最小费用最大流。此时需要先使用消圈算法消去图上的负圈。

由于会存在负权边，只能使用spfa找最短路。

复杂度：\(O(nmf(s,t))\) 。

Prime-Dual算法

使用Johnson算法，使得可以在SSP算法基础上使用Dijkstra。

每次 \(h_u+=dis'_{s,u}\) ，其中 \(dis'_{u,v}=dis_{u,v}-h_v+h_u\) 。

复杂度：\(O(m\log nf(s,t)+nm)\)

capacity-scaling算法

capacity-scaling算法复杂度关于流量是弱多项式的。

算法流程：首先把图变成一个无源汇循环流。然后从大到小枚举一个 \(2^t\) ，每次求出 \(E_t=\{(u,v,\lfloor\frac{c}{2^t}\rfloor,w)|(u,v,c,w)\in E\}\)的费用流。

具体就是在 \(E_{t+1}\) 的基础上，把所有边流量 \(\times 2\)，然后需要给若干边流量加上一。

给 \((u,v)\) 加一时可以跑spfa找到从 \(v\) 到 \(u\) 的最短路，然后如果距离 \(<0\) 就增广。

复杂度：\(O(m^2 \log C)\)

练习题目

luoguP4123 [CQOI2016] 不同的最小割

每次任意找到两个点求最小割。

对于最小割分出的两个集合，分别递归继续求最小割。

容易发现任何分别处于源点集和汇点集的点对的最小割不可能大于当前求出来的最小割。

可以根据这个建一棵树，容易发现树上点对的答案就是路径边权最小值。

luoguP2472 [SCOI2007] 蜥蜴

最少有几只蜥蜴无法逃离=蜥蜴总数-最多有几只蜥蜴能逃离

对于每个点，将其拆分为入点和出点，将它们之间的容量设为该格子高度。对于可以跳出地图的点，将它们的出点与汇点连边，容量为 \(\infin\) 。对于所有起点，我们将源点和它们的入点连边，容量为 \(1\) ，最后跑最大流即可

luoguP4313 文理分科

经典最小割题。

先假设所有人文理都选，源点向每个人连接容量为 \(art\) 的边，每个人向汇点连接容量为 \(science\) 的边。这样每个人必须割掉一条边，表示放弃一种。

对于第二种收益，先假设全部获得。从源点连一条容量为 \(same_{art}\) 的边到一个辅助点，辅助点再向相邻的点连一条容量为 \(\infin\) 的边。这样要么放弃收益，要么有关的同学全部放弃理科。

第三种类似。

luoguP4177 [CEOI2008] order

如果这题没有组机器，那么直接跑最大权闭合子图

建边方式如下：

1. 源点向订单连流量为利润的边
2. 机器向汇点连流量为购买价格的边
3. 每个订单向需要的机器连流量为 \(\infin\) 的边

对于每个订单需要的相同机器，租用的价格不一样

考虑把 \(\infin\) 换成租机器的费用

最终建边方式如下：

1. 源点向订单连流量为利润的边
2. 机器向汇点连流量为购买价格的边
3. 每个订单向需要的机器连流量为租用费用的边

luoguP3980 [NOI2008] 志愿者招募

对于 \(\forall\ 1\leq i \leq n,i\in \bf Z^+\)，连 \((i,i+1,\infin−a_i ,0)\) 的边。对每类志愿者连 \((s_i,t_i+1,\infin,c_i)\) 的边。跑最小费用最大流即可