P3980 [NOI2008] 志愿者招募 题解

· · 题解

大部分题解只讲解了本题的建图方式并给出解释，少有题解真正讲明白这种看似奇妙建图的来源。

本题解将尝试不通过线性规划的方式，使用网络流语言讲明白本题的建图推导过程，并给出其背后的逻辑。

如果我们不满足于认识现有的结果，就要发掘出问题背后的脉络， 认识到看起来“神机妙算”的证明，拆掉之前的脚手架长什么样。

Carl Friedrich Gauss: “凡是有自尊心的建筑师，在瑰丽的大厦建成之后，决不会把脚手架留在那里。”

下文简记一条 x\to y 流量为 f，费用为 c 的边为 (x,y,f,c)。下文所有 \infty 指一个足够大的整数，取其为 10^{18}。

令第 i 天被覆盖了 t_i 次，题目限制即 \forall i,t_i\ge a_i，等价于 \min(t_i-a_i)\ge 0。

使用流量取 \min 的特性刻画 \min(t_i-a_i)，那么将所有天对应的边串在一起即可描述。具体地，令第 i 天对应点 i，i\to i+1 的流量为 t_i-a_i，S\to a_1,a_{n+1}\to T。那么我们要求最大流 \ge 0。

考察选择一个人 (l_i,r_i,c_i) 对流量的贡献。不妨考虑一种简单情况：l_i=r_i=j。

由于一条边的流量可以拆分为并联的多条边的流量之和，我们可以将原来流量为 t_i-a_i 拆为一条 -a_i 的边和一条 t_i 的边，其中 t_i 在 l_i=r_i 的情况下就是我们选了多少次这个人。

我们自然想到额外连一条 j\to j+1 流量为 \infty，费用为 c_i 的边。这样取一个人这条边流量 +1，并造成 c_i 的贡献。

实际上这是可以推广的。对于一个人 (l_i,r_i,c_i)，它会贡献点 [l_i,r_i] 的边的流量。由于将之前所述两条相邻 (j,j+1,\infty,c_i) 的边合并为一条 (j,j+2,\infty,c_i) 是等价的，我们可以想到连一条 (l_i,r_i+1,\infty,c_i) 的边。注意这里要覆盖 [l_i,r_i] 对应的所有边，包括 r_i\to r_i+1 的边。

由于我们不能连流量为 -a_i 的边，可以将其整体 +\infty，即连流量为 \infty -a_i 的边，要求最大流 \ge \infty。

我们只需要在汇点处限制最大流 \le \infty，即 n+1\to T 流量为 \infty，那么费用流算法就会在保证最大流取到 \infty 的情况下，使总费用尽量小，这是符合我们的要求的。

总结来看，建图：对于每天 (i,i+1,\infty-a_i,0)，对于每个人 (l_i,r_i+1,\infty ,c_i)，源汇点连边 (S,1,\infty,0),(n+1,T,\infty ,0)。使用费用流算法即可解决。

由此，我们看到了，本题中两个反常的建图方式的来源：