限量补给的旅程 — 补充题解¶
Codex（GPT-6）：本题的单调队列动态规划、费用流与次数状态建模、证明、实现和验证；动态规划与费用流为通用方法。
第一问：每单位油流向一个路段¶
仍排序并补齐起点、终点，令相邻位置距离为 \(d_i\) ，有效容量为 \(C\) .若有 \(d_i>C\) ，直接不可达。给每个站建立结点，另设源汇：
- 源到站 \(i\) ：容量 \(\min(s_i,C)\) ，费用 \(c_i\) ，表示购买。
- 站 \(i\) 到汇：容量 \(d_i\) ，费用零，表示这一段的消耗。
- 站 \(i\) 到下一站：容量 \(C-d_i\) ，费用零，表示开完这一段后剩下的油。
要求总流量 \(L=\sum_i d_i\) .所有消耗边容量之和恰为 \(L\) ，所以满流强制每段消耗都满足。在站点的流守恒说明购买量加到站余油等于本段消耗加离段余油；后者至多 \(d_i+C-d_i=C\) ，恰为油箱限制。反向还可把任意满流还原为合法购油计划。
由于价格非负，存在最低费用方案到达时剩油为零：按燃料实际消耗追溯，减少最终未用燃料的购买即可。这样不会违反库存、容量或到达条件。因此只考虑总购买 \(L\) 不损失最优性。每个源站购买量也不超过单次油箱容量，截断源边合法。
用带势能的逐次最短增广路求最小费用流。初始正向费用非负，零势能可用；每次 Dijkstra 后用有限距离更新势能，使可达残量边的约化费用非负。整数容量保证每次至少增广一单位，至多 \(L\) 次。流量不足即不可达。
第二问：每种次数下最多能剩多少油¶
按站扫描，用 \(fuel[t]\) 保存用 \(t\) 次加油后保留的最多余油，初始仅 \(fuel[0]=0\) .不买则保留；若有空间且有库存，购买到 \(\min(C,fuel[t]+s_i)\) ，更新 \(t+1\) .次数从大到小更新，防止同站重复购买。随后减去下段距离，负状态丢弃。
对于最少次数，给定同样的已用次数，更多余油支配更少余油：不买时继续保持优势，买时 \(\min(C,f+s)\) 对 \(f\) 单调。若更多油导致以后某次已无空间购买，可以省略那一次，得到不更多的次数。因此即使没有保留所有“恰好次数”的低油状态，也不会丢掉最少次数答案。终点取仍可达的最小 \(t\) .
复杂度、贡献与取舍¶
图有 \(O(N+1)\) 个点边，费用流时间 \(O(L(N+1)\log(N+2))\) ，次数动态规划 \(O((N+1)^2)\) ，另加排序；空间 \(O(N+1)\) ，不分配按油箱容量索引的表。全部费用与势能使用 64 位整数。
该方案在正式数据上比油量单调队列慢，适合展示流量守恒与容量约束的建模，也便于独立核对费用最优值。时限已为两种完整方案留出实测余量。Codex（GPT-6）提出并实现 alternative.cpp。