网络流与建模问题

· · 算法·理论

一、写在前面

如果你不会写网络流的板子，可以参照网络流基础 - 洛谷专栏学习一下基础的最大流、费用流算法 Dinic。

”网络流建模，是将实际问题抽象成有向图上的流量分配问题，通过构建源点、汇点和中间节点表示对象关系，用“流”的观点和“费用“的观点限制条件约束，最终转化为求最大流、最小割、费用流、上下界流问题。关键在于识别问题的资源分配本质，并设计巧妙的构图方式（如拆点、设置容量/费用）来刻画约束与目标。“

——DeepSeek

其实网络流建模就是把一个复杂的规划问题转化成网络上的最大流/最小割/费用流等等问题。

问题里的限制、花费、选择都变成网络上的容量、费用、割。通过网络流解出问题的答案。

当然，如果刚学会写最大流，可以不用费劲理解上面这段话，只要做几道题感受一下就可以。网络流得题目建模多变，需要积累。

网络流的题目一般只考察建模，不考察时间或者考察很少；并且一般 Dinic 算法时间复杂度很难卡满，所以后面不再费心计算复杂度。

二、最大流的建模

这种问题限制较少，只要考虑最大流，不用引进费用。

1. 二分图最大匹配及其建模

（其实就是把问题建成二分图最大匹配，拿网络流算结果）

P3386 【模板】二分图最大匹配 - 洛谷

最大流求二分图最大匹配的流程如下：

  1. 建立源点 s，向左部每个点连容量为 1 的边。
  2. 建立汇点 t，从右部每个点向它连容量为 1 的边。
  3. 左右部间每一条边，连一条从左部指向右部的边，容量都是 1。
  4. 求这个图的最大流。匹配的边就是满流的边。

（图源罗勇军《算法竞赛》）

关于 Dinic 在这种网络上的时间复杂度：

这样比匈牙利算法更优。

下面这些题目都是建模成二分图最大匹配，可以用网络流：

（其实算是把二分图最大匹配的建模题收编到网络流了）

2. 圆桌问题

P3254 圆桌问题 - 洛谷

有来自 m 个不同单位的代表参加一次国际会议。第 i 个单位派出了 r_i 个代表。

会议的餐厅共有 n 张餐桌，第 i 张餐桌可容纳 c_i 个代表就餐。

为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。

直观感受，代表的分配像流。

要让同一单位来的代表不坐同一张桌子，就是一个单位的人去向一个桌子的最大容量是 1。

但是只有这些边还不行，要不然流没有来处去处，人数的限制也没考虑。

所以要与源点、汇点分别连边，表示人的总数限制。

具体来说，这么建图：

跑一遍最大流，如果源点到所有单位的边都满流，就有解。

至于方案，看每个单位连向哪张桌子的边满流，就表示人去了哪张桌子。

3. 教辅的组成

P1231 教辅的组成 - 洛谷

有 N_1 本书、N_2 本练习册和 N_3 份答案。已知书与练习册、书与答案之间的可能对应关系（两个二分图）。每本书最多只能与一本练习册和一份答案配对，从而组成一个完整书册（每册包含一本书、一本练习册和一份答案）。要求计算最多能组成多少个这样的完整书册。

N_1, N_2, N_3 \le 10^4。

对于数据点 1,2,3，1\le M_1,M_2\leq 20。

对于数据点 4\sim 10，1\le M_1,M_2 \leq 20000。

如果只有书和练习册，那么直接二分图最大匹配。

然而，只用类似匈牙利算法，我们不会三分图最大匹配。

那么肯定要转化成网络流。

但是，如果直接像二分图最大匹配那样连边，会出现这种情况：

图里每条边容量都是 1。

这种情况，总流量一共是 2，因为中间这本书组成了两套，肯定是不合法的。

所以，我们想要控制书对应点上的流量，但是网络流又不能控制点的流量。

所以说这时候得拆点，让它自己内部形成边，用边控制流量。

这样，书 和 书' 的边就能控制走过 书 的流量不超过 1。这样建图：

4. 最小路径覆盖问题

P2764 最小路径覆盖问题 - 洛谷

给定有向图 G=(V,E) 。设 P 是 G 的一个简单路（顶点不相交）的集合。如果 V 中每个顶点恰好在 P 的一条路上，则称 P 是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个定点开始，长度也是任意的，特别地，可以为 0。G 的最小路径覆盖是 G 所含路径条数最少的路径覆盖。设计一个有效算法求一个 DAG（有向无环图）G 的最小路径覆盖。

对于 100\% 的数据，1\leq n\leq 150，1\leq m\leq 6000。

看到这道题，首先可以看到 DAG 的特性。但是顺着这个方向思考并不能得到什么结果。所以还是考虑从路径的方向入手。

像这样的一张图，最小路径覆盖可以是 1 \rightarrow 2, 3 \rightarrow 4，也可以是 1 \rightarrow 2 \rightarrow 4, 3。

从图中我们发现，开始可以把每个点看作一条单独的路径，每选择一条边，就是把它相邻的两条路径合并起来。最小化不相交的路径总数，就是尽可能多选边。

但是，每个点入度最多为 1，出度最多为 1。这就限制了我们选边。

也就是说，问题转化成尽可能多在图上选边，同时满足入度出度限制。

考虑从这里入手建模。但是直接建图不好处理点的限制，所以还是考虑拆点。

一条边必定给一个点贡献 1 的入度，给另一个点贡献 1 的出度。这样，可以把入度出度分别处理。

具体来说：

刚才例子的图如下：

这个网络的最大流就是最多能选的边。用总点数减去最大流就是最小路径覆盖。

回来想一想：为什么限定是 DAG？

因为一个 DAG 上的环也满足每个点入度出度都为 1，但是这个环明显可以不选一条边，还是合法的路径。多个环套在一起的时候，决策会十分困难。非 DAG 上解这个问题是 NP 困难的。

关于方案：方法有很多。比较简单粗暴的方法是用并查集合并满流的边的两端，表示它们所在的路径被合并了。同时维护路径起点。合并完了从路径开头走满流的边输出。

5. 魔术球问题

P2765 魔术球问题 - 洛谷

假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1，2，3，...的球

  1. 每次只能在某根柱子的最上面放球。

  2. 同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 n 根柱子上最多能放多少个球，并计算出方案。例如，在 4 根柱子上最多可放 11 个球。

--- 乍一看，这个题跟网络流半点关系都没有，但是要相信放在网络流 24 题里面是有原因的。 其实看到这个题目应该第一时间想到贪心。因为手模样例可以发现贪心可以得到最优解，而且可以想到一个柱子上能摆什么完全取决于顶上的球。 然而很多带反悔的贪心问题可以用网络流解决。 我们可以发现，问题其实是把尽可能多的球穿起来，也就是让球占据尽可能少的链。 同时，一大一小两个球，只有加起来是完全平方数，大的才能穿在小的后面。 可以这样想：对于每个点，从比它小的又能跟它放在一起的点向它连有向边。假设现在连了 $m$ 个；计算这张图的**最小路径覆盖**，就是这 $m$ 个球的最少柱子数目。 只知道固定球数的最小柱子数目还不够，还要知道给定柱子数目的最大球数。网络流的一个优点就是能够在加入新的边、点之后，结合之前的残量网络迅速得出新的最大流。因此我们每次加入一个点，结合之前的残量网络反复算最大流，一旦最小路径覆盖超过 $n$，说明刚才的点超过的限制，答案就是 $m - 1$。 输出方案不同于最小路径覆盖问题：这次我们知道路线一定从小的球走向大的球，表示柱子先放小球后放大球，所以打标记从小球开始 DFS 即可。 # 三、最小割的建模 这种问题往往包含“**选择**”，要用最小割中选哪几条边的问题解决。这种问题建模时最好先完全**忘掉**最大流最小割定理，直接按最小割建模，建模后才回头来用最大流求答案。 ## 1. 追查坏牛奶 Pollutant control [P1344 [USACO4.4] 追查坏牛奶 Pollutant Control - 洛谷](https://www.luogu.com.cn/problem/P1344) 给定一张有向图，求点 $1$ 与点 $n$ 之间的最小割和**此前提下的最小割边数目**。 对于 $100 \%$ 的数据，满足 $2 \le N \le 32$，$0 \le M \le 10^3$，$1 \le S_i \le N$，$1 \le E_i \le N$，$0 \le C_i \le 2 \times 10^6$。 --- 最小割很简单，直接套用最大流最小割定理求最小割即可。 最小割边数目： 这里引用一段[最小割 - OI Wiki](https://oi-wiki.org/graph/flow/min-cut/#割边数量)： > 如果需要在最小割的前提下最小化割边数量，那么先求出最小割，把没有满流的边容量改成 $\infty$，满流的边容量改成 $1$，重新跑一遍最小割就可求出最小割边数量；如果没有最小割的前提，直接把所有边的容量设成 $1$，求一遍最小割就好了。 编码的时候稍微注意：反向边和原边还是要当成一条边，如果原边剩余容量为 $0$，说明满流了，容量改成 $1$，反之改成 $\infty$。反向边都还原成初始的容量为 $0$ 的状态。 ## 2. [SHOI2007]善意的投票/[JLOI2010]冠军调查 [P2057 [SHOI2007\] 善意的投票 / [JLOI2010] 冠军调查 - 洛谷](https://www.luogu.com.cn/problem/P2057) 幼儿园里有 $n$ 个小朋友打算通过投票来决定睡不睡午觉。 虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。 我们定义一次投票的冲突数为下面两者相加： * 实际投票不同的好朋友对数。 * 自己实际投票和自己本来意愿不同的人数。 给出 $m$ 对好朋友关系，每位小朋友应该怎样投票，才能使冲突数最小？ 对于 $100\%$ 的数据，$2\le n\le300$，$1\le m \le \frac{n(n-1)}2$。 --- 冲突在于每位小朋友投哪一方的选择。 考虑用最小割建模。对于一个点，把它和源点汇点都连边。如果他意愿是 $1$，那从源点连的边边权是 $1$，连向汇点的是 $0$。反之亦然。这样，违背自己意愿就会让最小割增加 $1$。 一对朋友如果意愿不同，那么肯定一个属于 $s$ 的那一侧，一个属于 $t$ 的那一侧。根据割的定义，他们不能互相到达。这样要产生 $1$ 个冲突，所以在他们之间连双向的容量为 $1$ 的边，因为你不知道他们哪个属于 $s$ 的那一侧，哪个属于 $t$ 的那一侧。 最小割就是答案。 ## 3. 方格取数问题 [P2774 方格取数问题 - 洛谷](https://www.luogu.com.cn/problem/P2774) 有一个 $m$ 行 $n$ 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 100$，$1 \leq a_{i, j} \leq 10^5$。 --- 这种题目用了一类很经典的建模方法：**方格黑白染色**。 把整个格子图染成国际象棋棋盘一样的**黑白相间格子**。白格子周围都是黑格子，反过来也一样。 可以发现，选了一个白格子，它周围的黑格子就不能再选。反过来也一样。 选的格子越多，不选的格子越少（这不是句废话吗）。用割掉的边代表不选的格子，求最小割。 一个格子选了，它的邻居就不能选。如果保留了这个格子的边，它邻居的边就必须切断。所以要把他们之间连上不能切断的边。 考虑这样连边： - 从源点向每个白格子连边，容量是白格子上的数字。 - 从每个黑格子向汇点连边，容量是黑格子上的数字。 - 从每个白格子向周围黑格子连边，容量是 $\infty$。 这样，选了一个白格子，因为它向周围黑格子连的边容量是 $\infty$，不能切断，所以必须切断这些黑格子向汇点连的边。 最小割就是不选的格子。用所有格子数字的总和减去最小割就是答案。 [P3355 骑士共存问题 - 洛谷](https://www.luogu.com.cn/problem/P3355) [P4304 [TJOI2013] 攻击装置 - 洛谷](https://www.luogu.com.cn/problem/P4304) 上面这两个题目几乎一样，只有以下几点改动： - 对于每个点，和它互斥的点变化了，变为“日”字形，但是仍然满足每个点的互斥点在**黑白相间染色**之后，和这个点颜色相反。 - 权值都是 1。（这一点更简单了） ## 4. 小 M 的作物 [P1361 小M的作物 - 洛谷](https://www.luogu.com.cn/problem/P1361) 小 M 在 MC 里开辟了两块巨大的耕地 $A$ 和 $B$（你可以认为容量是无穷），现在，小 P 有 $n$ 种作物的种子，每种作物的种子有 $1$ 个（就是可以种一棵作物），编号为 $1$ 到 $n$。 现在，第 $i$ 种作物种植在 $A$ 中种植可以获得 $a_i$ 的收益，在 $B$ 中种植可以获得 $b_i$ 的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小 M 找到了规则中共有 $m$ 种作物组合，第 $i$ 个组合中的作物共同种在 $A$ 中可以获得 $c_{1,i}$ 的额外收益，共同种在 $B$ 中可以获得 $c_{2,i}$ 的额外收益。 小 M 很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？ 对于 $100\%$ 的数据，$1 \le k < n \le 10^3$，$1 \le m \le 10^3$。题目当中出现的所有权值均为不大于 $1000$ 的非负整数。 --- 种在哪片地里面也是一种“选择”。可以用最小割建模。 第 $i$ 种作物在 $A$ 中种植可以获得 $a_i$ 的收益，在 $B$ 中种植可以获得 $b_i$ 的收益；所以从源点向 $i$ 连一条容量为 $a_i$ 的边，从 $i$ 向汇点连一条容量为 $b_i$ 的边。割掉较小的边，留下的就是选择的较大的边。结合上面的方格取数，可以看出，需要**做选择来让价值最大**时，常常用最小割计算**放弃的最小价值**。 这样就处理好了作物种植的问题。 多种植物间作的问题比较难。先以在 $A$ 中为例： - 建立一个额外点 $P$，向组合里的植物连容量为 $\infty$ 的边。 - 从 $s$ 向 $P$ 连容量为 $c_{1,i}$ 的边。 为什么可以这样？ $P$ 向组合里的植物连的边不能被割断。这样，只有在所有组合里的点都和 $t$ 不连接的时候，也就是所有点都选择在 $A$ 中的时候，才可以保留从 $s$ 向 $P$ 连的边。这时所有保留的边都在 $s$ 一侧，表示 $c_{1,i}$ 的边也一样，这个结构里没有向 $t$ 的边，保证了结果是割。 在 $B$ 中的类似： - 建立一个额外点 $P$，组合里的植物向它连容量为 $\infty$ 的边。 - 从 $P$ 向 $t$ 连容量为 $c_{2,i}$ 的边。 举例：下面的图就是只有两种作物，它们构成一个组合的情况。边权分别按上面所说一一对应。 ![](https://cdn.luogu.com.cn/upload/image_hosting/fo8j3cea.png) 求出最小割，用所有价值的和减去舍去的价值，就是答案。 ## 5. 最大权闭合子图 给定一张有向图，每个点都有一个权值（可以为正或负或 $0$)，你需要选择一个权值和最大的子图，使得子图中没有边指向子图外。 --- 没有边指向子图外，有关选择的问题，满足最小割的特点。 - 从源点 $s$ 向所有正权点（权值为 $w_i$）连边，容量为 $w_i$。 - 从所有负权点（权值为 $w_i$）向汇点 $t$ 连边，容量为 $-w_i$。 - 原图中的依赖关系（边）保留，容量设为无穷大（表示不可割）。 计算这张图的最小割，用所有正权值的和减去最小割就是答案。 证明： 1. **源点 $s$ 连所有正权点**（容量 = $w_i$） - 如果这个边被割掉，代表**不选**这个正权点（损失收益 $w_i$）。 2. **所有负权点连汇点 $t$**（容量 = $w_i$） - 如果这个边被割掉，代表**选**了这个负权点（$w_i < 0$，付出代价 $w_i$）。 3. **原图的依赖关系（边）容量设为无穷大** - 保证这些边**不会被割**（最小割不会割无穷大的边）。 - 这意味着：如果选了一个点，它指向的所有点**必须被选**（否则会通过无穷边形成通路，必须割掉某些边来断开）。 任何一个合法的子图都对应一个割，割的 $S$ 集合对应我们选择的子图。 每舍弃一个正权点，就割去 $s$ 与它连的边。每选取一个负权点，就割去它与 $t$ 连的边，也就是付出了对应权值的代价（因为我们把边容量设成相反数）。最小割对应我们**舍弃的正权点**和**选取的负权点**的最小权值和。 我们知道，答案 = 选取的正权值之和 + 选取的负权值之和 = （所有正权值之和 - 舍弃正权值之和）+ 选取的负权和 = 所有正权值之和 -（舍弃正权值之和 - 选取负权值之和） = 所有正权值之和 -（舍弃正权值之和 + 选取负权值的**绝对值**之和） 右边括号内的式子是割的数值，最小割保证右边式子最小。这样整个答案就最大。 ### 例：[NOI2006] 最大获利 [P4174 [NOI2006] 最大获利 - 洛谷](https://www.luogu.com.cn/problem/P4174) 公司得到了一共 $N$ 个可以作为通讯信号中转站的地址：建立第 $i$ 个通讯中转站需要的成本为 $P_i$（$1 \leq i \leq N$）。 另外公司调查得出了所有期望中的用户群，一共 $M$ 个。关于第 $i$ 个用户群的信息概括为 $A_i$，$B_i$ 和 $C_i$ ：这些用户会使用中转站 $A_i$ 和中转站 $B_i$ 进行通讯，公司可以获益 $C_i$。（$1 \leq i \leq M$，$1 \leq A_i, B_i \leq N$） 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和） --- 显然可以把每个用户群建一个点，连向需要的两个中转站。用户群的权值是收益，中转站的权值是成本（负的）。 在这张图上求解最大权闭合子图即可。 再给出一道例题，解法基本相同：[P2762 太空飞行计划问题 - 洛谷](https://www.luogu.com.cn/problem/P2762) # 四、费用流的建模 这类建模比较复杂。它既涉及容量的建模问题，也涉及费用的建模问题。问题中同时包含“限制”和“代价”，要通过拆点、附加边等技巧处理特殊约束（如节点容量、时间维度）。它也是网络流建模问题中最难的一部分。 下面用 $(u, v, w, c)$ 表示从 $u$ 到 $v$ 连了一条容量为 $w$，费用为 $c$ 的边。 ## 1. 费用流求二分图最大权匹配 问题简述：给定一张带权二分图，求所有可能匹配中权值最大的可能。 **最大权匹配的首要目标是所有匹配边的权重之和最大，而不是匹配边的数量最多。** --- 与求解二分图最大匹配类似，二分图的最大权匹配同样可以通过网络流进行求解。 具体建模方法如下： - 从源点向每个左部点 $L$ 连接一条边 $(s, L, 1, 0)$；从每个右部点 $R$ 向汇点连接一条边 $(R, t, 1, 0)$，表示每个左部/右部点只能选一次。 - 对于二分图中每一条从左部点 $u$ 向右部点 $v$ 的权重为 $w$ 的边，在网络中相应建立一条边 $(u, v, 1, w)$，表示选这个边。 在网络上求**最大费用最大流**，费用就是答案。 此外，由于图中可能发生一个点无论怎样匹配贡献都是负数，所以要允许一个点不匹配。为了允许部分左部点不参与匹配，还需从每个左部点向汇点额外连接一条容量为 $1$、费用为 $0$ 的边。这条边可以帮我们在最大流的前提下放过流不走负权边，从而允许一些点不匹配。 时间复杂度： 一般费用流的时间复杂度是 $O(nmf)$，此处最大流和点数同级（$f=O(n)$），所以时间复杂度是 $O(n^2m)$，略大于匈牙利算法；但同样，因为 SPFA 在随机图上表现良好，所以费用流一般很少跑满，所以实际使用可以减少学习成本。 ## 2. 分配问题 [P4014 分配问题 - 洛谷](https://www.luogu.com.cn/problem/P4014) 有 $n$ 件工作要分配给 $n$ 个人做。第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{ij}$ 。试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案，使产生的总效益最小或最大。 $1 \leq n \leq 50, 0 \le c _ {i, j} \le 100$。 --- 显然是二分图最大权匹配。 一个小技巧：既然所有边权都非负，那就可以不用从每个左部点向汇点额外连接边。 建好图直接求最大费用最大流即可。 ## 3. 运输问题 [P4015 运输问题 - 洛谷](https://www.luogu.com.cn/problem/P4015) $W$ 公司有 $m$ 个仓库和 $n$ 个零售商店。第 $i$ 个仓库有 $a_i$ 个单位的货物；第 $j$ 个零售商店需要 $b_j$ 个单位的货物。 货物供需平衡，即 $\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$。 从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用为 $c_{i,j}$ 。 试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。 $1 \leq n, m \leq 100$。 --- 货物的运输过程可以建模成流。运送过程的费用就是流的费用。 具体来说： - 对于每个仓库 $i$，从源点连 $(s, i, a_i, 0)$。让每个仓库能获得 $a_i$ 的流量。 - 对于每个仓库 $i$ 和商店 $j$，连 $(i, j, \infty, c_{i,j})$，表示从仓库 $i$ 到商店 $j$，运货多少没有上限，费用是 $c_{i,j}$。 - 对于每个商店 $j$，向汇点连 $(j, t, b_j, 0)$。让每个商店能排出 $b_i$ 的流量。 完成后分别跑最小费用、最大费用最大流。费用就是答案。 ## 4. 方格取数加强版 [P2045 方格取数加强版 - 洛谷](https://www.luogu.com.cn/problem/P2045) 给出一个 $n\times n$ 的矩阵,每一格有一个非负整数 $A_{i,j}$（$A_{i,j} \le 10^3$），现在从 $(1,1)$ 出发，可以往右或者往下走，最后到达 $(n,n)$，每达到一格，把该格子的数取出来，该格子的数就变成 $0$，这样一共走 $K$ 次，现在要求 $K$ 次所达到的方格的数的和最大。 $1 \le n \le 50$，$0 \le K \le 10$。 每个格子中的数不超过 $1000$。 --- 网络流很难在点上设置贡献，所以考虑拆点。把每个点（格子）拆成上下两个点 $u$ 和 $u'$，约定每次只能从 $u$ 走向 $u'$，就算经过了这个点。 这样，连一条 $(u, u', 1, A_{i,j})$，表示这个点经过的第一次可以取 $A_{i,j}$作为贡献。再连 $(u, u', \infty, 0)$，表示后面可以无限次经过这个点，但是没有贡献。 每个点 $u$ 可以走到右下方的两个点。因为走点内部的时候约定了从上走到下，所以从这个点出来之后进入那个点，就表示成 $(u', v, \infty, 0)$，这里 $v$ 是 $u'$ 右边或下边的邻居。 再考虑流量限制。连 $(s, (1,1), K, 0)$ 表示最多出 $K$ 次，同样，连 $((n, n), t, K, 0)$。 求最大费用最大流，费用就是答案。 类似的练习：[P3356 火星探险问题 - 洛谷](https://www.luogu.com.cn/problem/P3356) ## 5. [SCOI2007]修车 [P2053 [SCOI2007] 修车 - 洛谷](https://www.luogu.com.cn/problem/P2053) 同一时刻有 $N$ 位车主带着他们的爱车来到了汽车维修中心。 维修中心共有 $M$ 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。 现在需要安排这 $M$ 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。 对于 $100\%$ 的数据，$2\le M\le 9$，$1\le N\le 60$，$1\le T\le 10^3$。 --- 首先平均等待时间可以转化成总等待时间。 如果不考虑等待的问题，只按修车时间统计答案，那么直接在每对车和人之间连边，跑最小费用最大流就行了。 但是等待的问题不能忽略，这也正是这道题的难点。 题目表明，一位顾客等待时间是他前面所有人（包括他自己）修车的总时间。我们想最小化这个时间。 如果每个人的修车时间是 $t_1,t_2,t_3,\dots,t_k$，那么所有人的总等待时间是： $$ t_1+(t_1+t_2)+(t_1+t_2+t_3)+\dots+(t_1+t_2+t_3+\dots+t_k)\\ =kt_1+(k-1)t_2+(k-2)t_3+\dots+t_k $$ 可以观察到，师傅给 $k$ 个人中的**倒数**第一个人修车时，对总等待时间产生的贡献是 $t_k$，给**倒数**第二个修的时候是 $2t_{k-1}$；以此类推，如果一辆车维修时间是 $t_{now}$，排在**倒数**第 $a$ 个位置，那么这一项对时间的贡献就是 $a\cdot t_{now}$，不仅和修车人有关，还和位次有关。 所以，考虑把人拆成 $N$ 个，每个分别只修一辆车，依次是**倒数**第 $1$ 个，第 $2$ 个，第 $3$ 个，……第 $N$ 个，对于修**倒数**第 $a$ 辆车的人，从每辆车都连边指向它，容量为 $1$ 表示只修一辆车，但是时间要乘以 $a$。 然后连源点指向车的边，限制每辆车只被修一次；同理，从每个拆开的人连向汇点。 跑最小费用最大流。费用就是答案。 ## 6. 餐巾计划问题 [P1251 餐巾计划问题 - 洛谷](https://www.luogu.com.cn/problem/P1251) 一个餐厅在相继的 $N$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾（$i = 1, 2, \dots, N$）。餐厅可以购买新的餐巾，每块餐巾的费用为 $p$ 分；或者把旧餐巾送到快洗部，洗一块需 $m$ 天，其费用为 $f$ 分；或者送到慢洗部，洗一块需 $n$ 天（$n \gt m$），其费用为 $s$ 分（$s \lt f$）。 每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。 试设计一个算法为餐厅合理地安排好 $N$ 天中餐巾使用计划，使总的花费最小。编程找出一个最佳餐巾使用计划。 对于 $100 \%$ 的数据，$1 \le N \le 2 \times 10^3$，$1 \le r_i \le 10^7$，$1 \le p, f, s \le 10^4$。 --- 每天，餐厅后勤都要早上向外输出干净餐巾，再在晚上接收脏餐巾。如果不拆点，那么流没法区分干净餐巾和脏餐巾。 所以可以把每一天拆成两个点：早上和晚上。 对于早上：要供应干净餐巾。 - 每一天**早上** $u$ 要连接 $(u, t, r_u, 0)$，表示每天产出的干净餐巾。 - 每天可以直接购买餐巾，所以连 $(s, u, \infty, p)$ 表示每天可以买无限多的餐巾，但是要付费。 - 每天可以把干净餐巾留到下一天用。连 $(u, u + 1, \infty, 0)$，表示把餐巾留给明天。最后一天不用连。 对于晚上：要处理脏餐巾。 - 每一天**晚上** $u'$ 要连接 $(s, u', r_u, 0)$，表示每天接收的脏餐巾。 - 每天可以把餐巾送去快洗/慢洗。连 $(u', u + m, \infty, f)$ 表示慢洗，再连 $(u', u + n, \infty, s)$ 表示快洗。也就是耗费费用把**晚上**的餐巾送到对应某一天的**早上**。 - 每天还可以囤积脏餐巾以后再洗。连 $(u', u' + 1, \infty, 0)$ 表示把脏餐巾留到后一天。最后一天不用连。 完成之后跑最小费用最大流，费用就是答案。 有人问：建模并没有限制每天必须供应这么多餐巾，也就是没有限制满流。怎么办？ 答：最大流一定会把每条有上限的边（表示干净餐巾供应的边）跑满，因为别的边容量都是 $\infty$。也就是说这时候一定是供应完全的最小费用。如果考场上遇到了还是担心，可以添加下限写成最小费用可行流。 关于加强版：[P4480 [BJWC2018] 餐巾计划问题 - 洛谷](https://www.luogu.com.cn/problem/P4480) 对于 $100\%$ 的数据，$1 \leq n \leq 200000$ ， $1 \leq m_1, m_2 \leq n$ ， $1 \leq c_1, c_2, p \leq 100$ ， $1 \leq r_i \leq 100$ 。 建模不变，需要优化： - 加快读。 - 题目没有保证，两种洗法中没有一个比另一个严格更优（费用又低速度又快）。所以如果出现了这种情况，不必连慢洗的边。 - 计算发现，所有数据都可以用 int。 - **给 SPFA 加上 SLF 和 LLL。** 这样就可以过了。我的代码总时间 1.48s，最慢点 761ms。 ## 7. 剪刀石头布 [P4249 [WC2007] 剪刀石头布 - 洛谷](https://www.luogu.com.cn/problem/P4249) 题意简述： 有一张 $n$ 个点的竞赛图（任意两点之间只有一条有向边的完全图），其中有些边指向已知（有向边），有些边指向未知（无向边）。 要求给这张图每条边定向，使得最终竞赛图中**三元环**数量最多。输出最多的数量和分配方案。原图、最优方案以胜负表格的形式输入/输出。$n \le 100$。 --- 先观察三元环/非三元环和竞赛图的性质。 一个三元环，必定每个点入度都是 $1$。一个非三元环，必定有一个点入度是 $2$，一个点出度是 $2$，一个点入度出度都是 $1$。 再观察下面的图： ![](https://cdn.luogu.com.cn/upload/image_hosting/kc2kkre5.png) 这张图上，如果只看 $1$ 号点，它的入度是 $3$。因为它的存在，$(1,2,3),(1,2,4),(1,3,4)$ 都不是三元环。究其原因，是因为它的**每两条入边**就会消除一个三元环。所以，这个点一共消除了 $C_3^2 = 3$ 个三元环。推广出去，如果一个点的入度是 $\deg$，那么它会消除 $C_{\deg}^2$ 个环。 另一方面，如果一个点入度已经是 $\deg$，新定向一条边指向它，那么这条新边会与之前的所有 $\deg$ 条入边配对，又消除 $\deg$ 个三元环；入度也更新为 $\deg + 1$。 如果能根据这个特点规划出最优解下每个点的入度，就可以这么计算环的个数： 一张 $n$ 个点的竞赛图中，**三元组**的个数是 $C_n^3=\dfrac{n(n-1)(n-2)}{6}$。每个点 $u$，如果入度是 $\deg _u$，就会消除 $C_{\deg _u}^2$ 个环。所以，三元环的个数是 $C_n^3 - \sum_u C_{\deg _u}^2 = \dfrac{n(n-1)(n-2)}{6} - \sum_u \dfrac{\deg _u(\deg _u - 1)}{2}$。 三元环尽量多，就是尽量少消除三元环。 先不考虑有向边，只看无向边对答案的影响。 一条无向边指向哪里，哪里的入度就增加一。如果这一步时这个点入度已经是 $\deg$，那么这一步消除 $\deg$ 个三元环，这是我们已经知道的。那么，可以考虑这样规划费用： - 每条边要对应一个点 $e$。连 $(s, e, 1, 0)$ 表示给这条边一个选择方向的机会。 - 连 $(e, u, 1, 0), (e, v, 1, 0)$，表示每条边**只能**给其中一个点一个入度。$u,v$ 是原图中这条边连接的两个点。 - 对于每个点 $u$，依次连 $(u, t, 1, 0), (u, t, 1, 1), (u, t, 1, 2) \dots (u, t, 1, n)$。第一条边表示原来入度为 $0$，这条边不会消除任何一个三元环。第二条边只有在第一条边被占用时才派上用场。它表示原来入度已经有 $1$ 了（前面占满了 $1$ 条边），现在再加一个入度会消除 $1$ 个三元环。以此类推…… 这样跑最小费用最大流，得到的就是最优结果。费用表示被迫消除了几个三元环。 但是有向边怎么办？ 有向边产生的入度已经固定。先统计出有向边产生的入度。对于一个点 $u$，不连 $(u, t, 1, 0), (u, t, 1, 1), (u, t, 1, 2) \dots (u, t, 1, n)$，而是连 $(u, t, 1, \deg), (u, t, 1, \deg + 1), (u, t, 1, \deg + 2) \dots (u, t, 1, n)$。这就表示原先已经有 $deg$ 条入边，新增入边的影响当然要从 $\deg$ 开始计算。 但是，虽然费用代表了消除的三元环，但是不能直接用费用计算答案，因为原有向边也产生了三元环。有两种方法： 1. 计算原有向边的三元环个数，用 $C_n^3$ 减去费用和原来的个数。 2. 结束后统计出每个点的入度，根据最优解的入度直接计算答案。 对于方案输出： 每个无向边对应的点，流量流到了哪里，就代表这条无向边要指向它。遍历这些点，在残量网络上观察它们的流向，在胜负表格上标注即可。 # 五、总结 ## 关于上下界网络流 这篇文章最大的缺点就是，因为篇幅和我的时间精力限制，没有提到上下界网络流建模问题。在我的[网络流基础 - 洛谷专栏](https://www.luogu.com.cn/article/4pkn7ylz)中也没有写上下界网络流的算法。然而，这个知识点并非不重要。许多普通题目、省选题目、**NOI** 题目都考了这个知识点。如果一个题目既能建模成上下界网络流，又能建模成最大流/费用流，那么一般上下界的建模思维含量更低，因为高科技能代替思考。就像区间加区间求和时，树状数组艰难的思维转换被线段树虽然有难度但是成型的板子替代。这几篇上下界网络流文章比较好，可以作为补充： - [上下界网络流 - OI Wiki](https://oi-wiki.org/graph/flow/bound/) - [算法学习笔记(60): 上下界网络流 - 知乎](https://zhuanlan.zhihu.com/p/324507636) - [详细且适合入门的上下界网络流详解 - 知乎](https://zhuanlan.zhihu.com/p/1942933976521117940) 这些题目可以用上下界网络流建模： - [P5192 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流 - 洛谷](https://www.luogu.com.cn/problem/P5192) - [P4843 清理雪道 - 洛谷](https://www.luogu.com.cn/problem/P4843) - [P4553 80 人环游世界 - 洛谷](https://www.luogu.com.cn/problem/P4553) - [P4043 [AHOI2014/JSOI2014] 支线剧情 - 洛谷](https://www.luogu.com.cn/problem/P4043) - [P3980 [NOI2008] 志愿者招募 - 洛谷](https://www.luogu.com.cn/problem/P3980) - [P2304 [NOI2015] 小园丁与老司机 - 洛谷](https://www.luogu.com.cn/problem/P2304) 网络流的板子虽然也有一定难度，但是往往在建模题中不会考察过于高深的最大流/费用流算法，只需要 Dinic 即可。并且，就像开头所说，网络流题一般也对时间限制不是很严格。所以重点应该放在积累建模技巧上。 另外，网络流的题目往往因为板子难度高而轻易评紫，所以要注意对自己实力的评估，做出很多甚至迅速切掉很多网络流紫题并不能说明自己就一定能切掉其他方向的紫题，尤其是思维含量高的紫题。 最后，我前面讲得一板一眼，但其实缺乏积累，很多经典题目都没有涉及，可见水平有限。大家如果看到我表达不清楚或者有问题，请尽快指出或询问，非常感谢。