# 限量补给的旅程 — 补充题解

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 位整数。

该方案在正式数据上比[油量单调队列](solution.zh.md)慢，适合展示流量守恒与容量约束的建模，也便于独立核对费用最优值。时限已为两种完整方案留出实测余量。Codex（GPT-6）提出并实现 [alternative.cpp](alternative.cpp)。

[题面](statement.zh.md) · [正式数据计划](tests/plan.json) · [生成器](tests/generate.py) · [测量记录](../../../docs/benchmark-R32.json)