浅谈上下界网络流

· · 算法·理论

上下界网络流

上下界网络流，即每条边的容量可以有上界和下界。其实普通的网络流容量就是有上界的。所以重点是下界如何处理。基本的处理方法是，通过源点和汇点实现“强制流过”的效果。具体来说，对于原图中的一条边 (u,v)，有容量下界 l，容量上界 r。用 s, t 表示源点和汇点。则在新图中改为

因为直接连到起点、终点的边可以通过求最大流的方式强制满流。于是 v 处会有 l 的流量必须流走，u 处必须流入 l 的流量，这就起到了强制流过的效果。上下界之间的容量不需要特殊处理，直接保留。

下面介绍上下界网络流经常出现的一些形式：

无源汇上下界可行流

没有源点和汇点，每条边给出一个容量上下界，问是否存在合法流（合法流即满足容量限制和流量守恒）。

新建源点 s 和汇点 t，直接按照上面所说的方式建图，然后求 s 到 t 的最大流，判断最大流是否等于所有下界的和即可。

模板：P14578。

有源汇上下界最大流

普通的最大流，容量有上下界的版本。设原图中源点为 s，汇点为 t。

从 t 向 s 连一条容量无限的边，这样就变成了无源汇的情况。然后新建超源 ss 和超汇 tt，按上面的方式建新图。这样能得到一个有源汇上下界可行流。

回到原图。我们现在有一个可行流，于是有一个残量网络，在这个残量网络上再跑 s 到 t 的最大流即可。注意答案要加上前面求出的可行流的答案。

注：从 t 向 s 连一条容量无限的边后，s 到 t 的流量实际上就是 t 到 s 的这条边的流量。

模板：P14579。

有源汇上下界最小流

同上面的做法，最后在残量网络跑 t 到 s 的最大流。

模板：P14580。

上下界费用流

把所有最大流改为费用流即可。

有负圈的费用流

普通的最小费用最大流，但是存在负费用的环，导致最短路 EK 无法运行。

把负费用看成收益，先强行取走，然后允许反悔。

具体来说，对于一条边 (u,v)，容量为 c，费用为 w。如果 w<0，则

这样处理之后，所有费用都是非负数，直接跑最短路 EK 即可。

注：正费用边要保持不变。

注：如果一个带费用的网络一开始没有负圈，那么在最短路 EK 的过程中是不会因为增广引入负圈的。

注：听说有消圈算法：while(找到负圈) 沿着负圈增广，直到没有负圈为止。每次找负圈的复杂度显然是 O(nm)，但是不知道要运行几轮，时间复杂度好像没有保证。不建议使用。

模板：P7173。

无源汇最小费用流/最小费用循环流

没有源点和汇点。每条边有容量和费用（有负费用），求这张图的最小费用流。

消圈。听说是假做法。

把负费用看成收益，先强行取走，然后允许反悔。

具体来说，新建源点 s 和汇点 t。对于一条边 (u,v)，容量为 c，费用为 w。如果 w<0，则

这样处理之后，所有费用都是非负数，直接跑最短路 EK 求最小费用流即可。注意不是最小费用最大流。

P5192 Shoot the Bullet | 东方文花帖

有 n 天，m 位少女。要为第 x 个少女拍摄至少 G_x 张照片。

第 i 天有 C_i 次拍摄机会。一次拍摄机会形如 (T,L,R)，表示你可以且必须给第 T 位少女拍摄照片，照片的张数在 [L,R] 内。同一天有可能有同一位少女的多次拍摄机会。

第 i 天一共只能拍摄不超过 D_i 张照片。

满足以上所有条件的基础上，拍摄尽量多的照片。

做法：每天建一个点，每次拍摄机会建一个点，另外建源点 s 和汇点 t。

源点向每天的点连边，容量为 D_i。

每天的点向当天的拍摄机会连边，容量有上下界 [L,R]。

每个拍摄机会向汇点连边，无容量限制。

然后跑有源汇上下界最大流即可。

P4843 清理雪道

给定一个 DAG，选择若干条链，使得每条边都被选中至少一次。问最少选择多少条。

做法：首先有费用流做法。每条边拆边，一条费用为负无穷，容量为 1，另一条费用为 0，容量为无穷。源点向每个点连边，每个点向汇点连边，都是费用为 0，容量为无穷。然后跑最小费用流即可。s 到 t 距离为 0 时停止。

考虑不需要费用流的做法。每条边至少要经过一次，考虑上下界。源点向每个点连边，每个点向汇点连边，容量为无穷。原图的每条边容量有下界 1 无上界。然后跑有源汇上下界最小流即可。

注：可以与 P2764 区分一下。

P4043 支线剧情

给定一个 n 个点的有向图，保证从 1 号点出发能到达其它所有点。要选择若干条从 1 号点出发的链，使得每个点都被经过至少一次。问最少选择多少条。

做法：首先要拆点变为分层图。每个点拆成 x 和 x'，x 向 x' 连边，原图中存在边 (x,y) 则从 x' 向 y 连边。

源点向 1 号点连边，其它所有点向汇点连边。给 (x,x') 这样的边添加容量下界 1，跑有源汇上下界最小流即可。

P4194 矩阵

给定一个整数矩阵 A[n\times m]，求一个矩阵 B[n\times m]，满足 \forall 1\le i\le n,1\le j\le m,B_{i,j}\in[L,R]，且使下式值最小：

\max\begin{cases}\displaystyle\max_{1\le j\le m}\left\{\left|\sum_{i=1}^n\left(A_{i,j}-B_{i,j}\right)\right|\right\}\\\displaystyle\max_{1\le i\le n}\left\{\left|\sum_{j=1}^m\left(A_{i,j}-B_{i,j}\right)\right|\right\}\end{cases}

做法：最大值最小，考虑二分答案 mid。

每行建一个点，每列建一个点。另外建源点 s 和汇点 t。

然后跑上下界可行流 check 即可。

CF704D Captain America

在平面直角坐标系上有 n 个点，你需要将每个点红蓝染色，将一个点染成红色的价格是 r，染成蓝色的价格是 b。

此外存在着 m 条限制 (t_i,l_i,d_i)，t_i=1 表示这条限制是“直线 x=l_i 上的点染成两种颜色的点数之差的绝对值不得大于 d_i”，t_i=2 表示这条限制是“直线 y=l_i 上的点染成两种颜色的点数之差的绝对值不得大于 d_i”。

你需要在满足这些限制的情况下找到一种花费最少的染色方案，或者报告无解。

输出方案。

做法：这道题数据范围较大，不能用费用流。

因为只有两种颜色，所以花费最少的方案就是让染某种颜色的点尽量少。不妨假设红色比蓝色贵，于是要染尽量少的红色。用流表示红色。

每行建一个点，每列建一个点。另外建源点 s 和汇点 t。

然后跑有源汇上下界最小流。

CF708D Incorrect Flow

给定一个 n 个点 m 条边的有向图，1 号点是源点，n 号点是汇点。每条边 e 给出了一个容量 c(e) 和流量 f(e)。输入的数字都是非负整数。

题目中输入的流可能不合法，也就是不满足容量限制 0\leq f(e)\leq c(e) 和流量守恒。

你要修改每条边的容量和流量。把每个数值增大 1 或减小 1 都要付出 1 的代价。问最少付出多少代价使得流合法。

做法：从 n 号点向 1 号点连边，让每个点的流量都守恒。

对于流量不守恒的点，强行让它守恒。具体来说，对于流入大于流出的点，从该点向 t 连边，对于流出大于流入的点，从 s 向该点连边。

考虑原图中的边。如果已经满足 f(e)\leq c(e)，则正向流 e(e)-f(e) 内的单位费用是 1，更多的部分单位费用是 2。反向流最多流 f (e)，单位费用是 1。

如果原图中的边满足 f(e)>c(e)，则先支付 f(e)-c(e) 的代价，将流量调整为 c(e)。正向流 f(e)-c(e) 内的单位费用是 0，更多的部分单位费用是 2。 反向流最多流 c(e)，单位费用是 1。

对于从 n 号点到 1 号点的边，应该只有正向流，且修改它应该没有代价。单位费用设为 0 即可。

然后跑 s 到 t 的最小费用最大流。

注：上面的做法不需要上下界，而且也很自然。我最先想到的是上面的做法。下面介绍题解学来的上下界的做法。

原图中边的部分保持不变。即

题目中给出的流需要保持。这里用上下界网络流。即对原图中的每条边 e=(u,v)，连边 (u,v,[f(e),f(e)],0)。

然后跑有源汇上下界最小费用可行流。

实际上这两个做法是等价的。