专栏文章

P3980 [NOI2008] 志愿者招募 题解

ll1ng21y12026
P3980题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimz4kbw
此快照首次捕获于
2025/12/01 17:55
3 个月前
此快照最后确认于
2025/12/01 17:55
3 个月前
查看原文
大部分题解只讲解了本题的建图方式并给出解释，少有题解真正讲明白这种看似奇妙建图的来源。
本题解将尝试不通过线性规划的方式，使用网络流语言讲明白本题的建图推导过程，并给出其背后的逻辑。
如果我们不满足于认识现有的结果，就要发掘出问题背后的脉络， 认识到看起来“神机妙算”的证明，拆掉之前的脚手架长什么样。
Carl Friedrich Gauss: “凡是有自尊心的建筑师，在瑰丽的大厦建成之后，决不会把脚手架留在那里。”
下文简记一条 x→yx\to y 流量为 ff，费用为 cc 的边为 (x,y,f,c)(x,y,f,c)。下文所有 ∞\infty 指一个足够大的整数，取其为 101810^{18}。
令第 ii 天被覆盖了 tit_i 次，题目限制即 ∀i,ti≥ai\forall i,t_i\ge a_i，等价于 min⁡(ti−ai)≥0\min(t_i-a_i)\ge 0。
使用流量取 min⁡\min 的特性刻画 min⁡(ti−ai)\min(t_i-a_i)，那么将所有天对应的边串在一起即可描述。具体地，令第 ii 天对应点 ii，i→i+1i\to i+1 的流量为 ti−ait_i-a_i，S→a1,an+1→TS\to a_1,a_{n+1}\to T。那么我们要求最大流 ≥0\ge 0。
考察选择一个人 (li,ri,ci)(l_i,r_i,c_i) 对流量的贡献。不妨考虑一种简单情况：li=ri=jl_i=r_i=j。
由于一条边的流量可以拆分为并联的多条边的流量之和，我们可以将原来流量为 ti−ait_i-a_i 拆为一条 −ai-a_i 的边和一条 tit_i 的边，其中 tit_i 在 li=ril_i=r_i 的情况下就是我们选了多少次这个人。
我们自然想到额外连一条 j→j+1j\to j+1 流量为 ∞\infty，费用为 cic_i 的边。这样取一个人这条边流量 +1+1，并造成 cic_i 的贡献。
实际上这是可以推广的。对于一个人 (li,ri,ci)(l_i,r_i,c_i)，它会贡献点 [li,ri][l_i,r_i] 的边的流量。由于将之前所述两条相邻 (j,j+1,∞,ci)(j,j+1,\infty,c_i) 的边合并为一条 (j,j+2,∞,ci)(j,j+2,\infty,c_i) 是等价的，我们可以想到连一条 (li,ri+1,∞,ci)(l_i,r_i+1,\infty,c_i) 的边。注意这里要覆盖 [li,ri][l_i,r_i] 对应的所有边，包括 ri→ri+1r_i\to r_i+1 的边。
由于我们不能连流量为 −ai-a_i 的边，可以将其整体 +∞+\infty，即连流量为 ∞−ai\infty -a_i 的边，要求最大流 ≥∞\ge \infty。
我们只需要在汇点处限制最大流 ≤∞\le \infty，即 n+1→Tn+1\to T 流量为 ∞\infty，那么费用流算法就会在保证最大流取到 ∞\infty 的情况下，使总费用尽量小，这是符合我们的要求的。
总结来看，建图：对于每天 (i,i+1,∞−ai,0)(i,i+1,\infty-a_i,0)，对于每个人 (li,ri+1,∞,ci)(l_i,r_i+1,\infty ,c_i)，源汇点连边 (S,1,∞,0),(n+1,T,∞,0)(S,1,\infty,0),(n+1,T,\infty ,0)。使用费用流算法即可解决。
由此，我们看到了，本题中两个反常的建图方式的来源：
  • 链式建图：为了刻画 min⁡(ti−ai)\min(t_i-a_i)，将边串在一起。
  • 一个人连一条跨过区间的边：实际上利用了流量的可拆分性和可合并性进行转化。
    即一条边的流量可以拆分为并联的多条边的流量之和；
    连一条跨过一段区间的、流量为 xx 的边等价于将区间内的所有边流量加上 xx。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...