# 4288 逃离塔科夫题解 **题目链接**：http://39.106.228.241/problem.php?id=4288 ## 题目大意在诺文斯克战乱区，你有 $N$ 个物资点（编号 $1\sim N$）和 $M$ 条单向暗道。从出生点 $S$ 出发，目标是抵达撤离点 $E$。 - 每个物资点 $i$ 的战利品价值为 $v_i$，**首次**踏入即可瞬间搜刮，且只能搜刮一次； - 通过暗道 $u \to w$ 需要消耗 $t$ 秒； - 累计行动时间**不能超过** $T$ 秒，否则判定"战局迷失"，一切归零； - 题目保证地图是 **DAG**（无环），且 $S$ 到 $E$ 至少存在一条可行路径。求在时限内能带出撤离点的**最大战利品总价值**。 **数据范围**：$N \le 100$，$M \le 200$，$t \le 1000$，$T \le 10^9$，$0 \le v_i \le 10^5$。 ## 思路 ### 1. 两个关键观察 **观察一：每个点只会被搜刮一次是自然满足的。** 因为图是 DAG，$S \to E$ 的任意一条简单路径上不可能重复经过某个点（否则就会形成环）。所以在一条路径上"首次踏入 = 唯一一次踏入"。 **观察二：$T$ 高达 $10^9$，不能按时间做维度 DP。** 如果设 $f[t][u]$ 表示"耗时恰好 $t$ 到达 $u$ 的最大价值"，时间维度根本开不下。经典做法是**把时间和价值当作两个坐标**，用"帕累托前沿"来压缩状态。 ### 2. 帕累托前沿 DP 对每个点 $u$，维护一个状态集合 $f[u]$，每个状态是二元组 $(\text{time}, \text{value})$，表示某条 $S \to u$ 的路径的（累计耗时, 累计价值）。 **支配关系**：若状态 $A = (t_a, val_a)$、$B = (t_b, val_b)$ 满足 $t_a \le t_b$ 且 $val_a \ge val_b$，则 $B$ 永远不比 $A$ 优 —— 无论之后怎么走，$A$ 的后续任何路径，$B$ 都能用不更差的时间得到不更差的价值。**$B$ 是冗余的，可以直接丢弃。** 因此每个点的状态集在排序去支配后是"**时间递增、价值严格递增**"的阶梯形状： - 按 time 升序排序； - 相同 time 只保留 value 最大的； - 从左往右扫描，value 没有严格变大（即 $\le$ 上一个保留状态的 value）的状态直接丢弃。 ### 3. 转移按**拓扑序**处理每个点 $u$： 1. 先把 $f[u]$ 去支配，得到干净的前沿； 2. 对前沿中的每个状态 $(\text{time}, \text{value})$ 和每条出边 $u \to w$（耗时 $t$），生成新状态 $(\text{time} + t,\ \text{value} + v_w)$ 推入 $f[w]$。最后在 $f[E]$ 中，取所有 $\text{time} \le T$ 的状态中 value 的最大值，即为答案。 **为什么沿拓扑序转移是对的？** DAG 上所有 $S \to u$ 的路径都只经过拓扑序在 $u$ 之前的点，所以处理到 $u$ 时它的状态已经收集完整；而且转移只会从前面推到后面，不会回环。 ### 4. 复杂度分析设 $K$ 为单个点帕累托前沿的最大大小。对每个点要排序+去支配，并对每条出边遍历一次前沿： $$O\Big(\sum_{u} K\log K + K \cdot \text{outdeg}(u)\Big) = O\big((N+M)K\log K\big)$$ 在 $N \le 100,\ M \le 200$ 的数据范围下 $K$ 很小（实际远小于路径数，这正是去支配的威力），轻松通过。 ## 样例验证样例输入： ``` 5 6 1 5 1500 100 200 150 300 500 1 2 400 1 3 200 2 4 500 3 4 300 4 5 600 3 5 1000 ``` 三条可行路径： | 路径 | 耗时 | 价值 | |------|------|------| | 1 → 2 → 4 → 5 | 1500 | 1100 | | 1 → 3 → 4 → 5 | 1100 | 1050 | | 1 → 3 → 5 | 1200 | 750 | 答案取最大值 $1100$。 ## C++ 代码 ```cpp #include using namespace std; typedef long long ll; typedef pair pll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, S, E; ll T; cin >> N >> M >> S >> E >> T; vector v(N + 1); for (int i = 1; i <= N; i++) cin >> v[i]; vector>> g(N + 1); vector indeg(N + 1, 0); for (int i = 0; i < M; i++) { int u, w; ll t; cin >> u >> w >> t; g[u].push_back({w, t}); indeg[w]++; } // 拓扑排序 queue q; vector topo; for (int i = 1; i <= N; i++) if (indeg[i] == 0) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); topo.push_back(u); for (auto &e : g[u]) if (--indeg[e.first] == 0) q.push(e.first); } // 帕累托前沿 DP vector> f(N + 1); f[S].push_back({0, v[S]}); for (int u : topo) { vector &fu = f[u]; if (fu.empty()) continue; sort(fu.begin(), fu.end()); // 去支配：time 升序，value 必须严格递增才保留；time 相同取最大 value vector clean; for (auto &p : fu) { if (!clean.empty() && clean.back().first == p.first) { if (clean.back().second < p.second) clean.back().second = p.second; continue; } if (clean.empty() || p.second > clean.back().second) clean.push_back(p); } fu.swap(clean); for (auto &p : fu) { for (auto &e : g[u]) { f[e.first].push_back({p.first + e.second, p.second + v[e.first]}); } } } ll ans = 0; for (auto &p : f[E]) if (p.first <= T) ans = max(ans, p.second); cout << ans << "\n"; return 0; } ``` ## 附：Python 对拍器写题解时用来暴力对拍验证正确性的脚本（随机 300 组数据与暴力枚举对比）： ```python from collections import deque def solve(n, m, S, E, T, v, edges): g = [[] for _ in range(n + 1)] indeg = [0] * (n + 1) for u, w, t in edges: g[u].append((w, t)) indeg[w] += 1 q = deque([i for i in range(1, n + 1) if indeg[i] == 0]) topo = [] while q: u = q.popleft() topo.append(u) for w, t in g[u]: indeg[w] -= 1 if indeg[w] == 0: q.append(w) f = [[] for _ in range(n + 1)] f[S].append((0, v[S])) for u in topo: fu = f[u] if not fu: continue fu.sort() clean = [] for t, val in fu: if clean and clean[-1][0] == t: if clean[-1][1] < val: clean[-1] = (t, val) continue if not clean or val > clean[-1][1]: clean.append((t, val)) f[u] = clean for t, val in clean: for w, tc in g[u]: f[w].append((t + tc, val + v[w])) ans = 0 for t, val in f[E]: if t <= T: ans = max(ans, val) return ans def brute(n, m, S, E, T, v, edges): g = [[] for _ in range(n + 1)] for u, w, t in edges: g[u].append((w, t)) best = 0 def dfs(u, time, val, visited): nonlocal best if u == E and time <= T: best = max(best, val) for w, t in g[u]: if w not in visited and time + t <= T: dfs(w, time + t, val + v[w], visited | {w}) dfs(S, 0, v[S], {S}) return best ``` ## 总结 - **一维 DP 开不下时，考虑二维"帕累托前沿"**：状态只保留非支配解，时间递增、价值严格递增； - 去支配是这类"时间/花费 + 价值/收益"双目标问题的通用武器，配合拓扑序在 DAG 上非常自然； - 注意本题的"每个点只能搜刮一次"在 DAG 上自动成立，不需要状压。