看到 [NOI2020]美食家 这个标题我的第一反应是这不是一道签到题而是一道非常典型的“DP 思路一眼就能看出来但数据范围逼着你必须上矩阵快速幂”的题。它把图上带权最长路、恰好 T 天、节点重复收益、单点事件加成四个要素揉在一起看起来像图论做起来像线性代数最后还夹带一点“事件排序”的工程感。适合正在备战竞赛、想系统学矩阵快速幂优化 DP 的同学反复咀嚼。我第一次做的时候拆点那一步卡了很久后来想明白“状态里必须保留天数余量”这件事整个题才豁然开朗。1. 这道题到底在问什么1.1 题面还原与关键信息整理题面可以压缩成这样一个模型有 n 个城市m 条单向道路每条道路有一个耗时 w范围是 1 到 5。你从 1 号城市出发要在第 T 天回到 1 号城市。每到达一个城市包括第 0 天所在的 1 号城市你会获得这个城市的美食愉悦值同一个城市多次到达愉悦值可以重复获得。除了这些基础收益还有 k 个“美食节”事件每个事件描述为在第 t_i 天如果当天结束时你在城市 c_i那么可以额外获得 y_i 愉悦值。最后要求的是“恰好第 T 天在城市 1”时的最大愉悦值如果无法做到输出 -1。这个题最迷惑人的地方是“恰好 T 天”。它意味着不能简单跑一个最长路因为最长路不会限定步数但也不能直接枚举天数因为 T 可以给到 1e9 的级别。你要找的本质上是一条“长度为 T 的路径”同时路径上每个节点的权值可以累积并且某些精确时间点上有额外奖励。1.2 数据范围决定了算法方向n 只有 50 左右m 也在 500 以下但 T 是 1e9 级别。这个数据范围组合非常明显图很小时间很长适合把“图上的状态转移”变成“矩阵的幂”。如果把每天当成一次转移那么朴素 DP 的复杂度是 O(T * m)T 一旦到 1e9 就完全不可行。但如果我们能构造出一个“转移一天”的矩阵那么连续走 T 天就等价于把这个矩阵乘 T 次。矩阵快速幂可以把 T 次压缩到 log T 次问题就转化为怎么把原题的天数转移写成一个矩阵并且让这个矩阵支持快速幂。这里有一个隐藏前提普通矩阵乘法只能处理“每次转移时间和权重都固定”的递推。原题的边权 w 不是 1所以走一条 w 天的边不能简单作为一步转移。于是就需要拆点。1.3 先给结论算法主线整道题的主线可以分成四步先写朴素 DP确认状态和转移是对的。把每个城市拆成 5 个状态用来表示“正在前往该城市的路上还剩几天”。用 max-plus 矩阵乘法代替普通矩阵乘法构造“一天转移矩阵”。把美食节事件按时间排序每两个事件之间用矩阵快速幂跳过去到点再单点加值。后面的所有内容都是围绕这四步展开的。2. 从朴素 DP 到矩阵快速幂2.1 最容易想到的 f[i][u]不考虑美食节时朴素 DP 是很好想的。设 f[i][u] 表示第 i 天结束时在城市 u 的最大愉悦值。初始化 f[0][1] val[1]。转移时枚举每条边 u - v边权为 wf[i w][v] max(f[i w][v], f[i][u] val[v])这个转移的意思很直白如果你第 i 天在 u走一条 w 天的路那么第 i w 天到达 v并获得 v 的愉悦值。这个 DP 的正确性没有问题问题在于 i 的范围太大。T 是 1e9哪怕 n 再小也没法真的开一个 1e9 的数组更不可能做 1e9 次转移。2.2 把 DP 写成向量和矩阵观察上面的转移它本质上是当前第 i 天的状态只决定第 i w 天的状态而且状态之间是“取最大值”的递推。如果能设计出一种“每次只前进一天”的转移那么就可以写成vector_i vector_{i-1} × Matrix其中 vector_i 是一个长度为 N 的向量N 是所有状态的数量。Matrix 的第 j 行第 k 列表示“从状态 j 经过一天到达状态 k 能获得的收益”。这里的关键是“经过一天”而不是“经过 w 天”。只要 Matrix 能完成“一天一天地推进”那么走 T 天就是 vector_0 乘以 Matrix 的 T 次方。2.3 max-plus 矩阵乘法是什么普通矩阵乘法里C[i][j] sum_k A[i][k] * B[k][j]。但我们要的转移是“取最大值”而不是“求和”所以需要换成 max-plus 乘法C[i][j] max_k (A[i][k] B[k][j])这个公式里原来的“乘法”变成了“加法”原来的“加法”变成了“取 max”。名字里的 max-plus 就是这么来的。为什么可以用它因为我们需要求的是路径收益的最大值而两条路径拼接时总收益等于两段收益相加。如果用普通矩阵乘法会把所有路径收益加起来那求的是路径数量或者某种和不是最大值。max-plus 矩阵乘法仍然满足结合律所以快速幂照样能用。这一点非常重要。快速幂依赖的核心性质就是结合律而不是普通乘法里的“乘加”结构。只要矩阵乘法满足结合律就能用倍增的方式预处理幂次。提示第一次接触 max-plus 时别把它想得太神秘。它只是把“状态可达性”从布尔矩阵换成了“最大收益”矩阵。矩阵的 k 次幂的第 i 行第 j 列含义是从状态 i 出发恰好走 k 步到达状态 j 能获得的最大收益。3. 拆点建模的完整细节3.1 为什么必须拆点普通矩阵快速幂每次只推进一天但原题边权 w 最大是 5。如果直接把边权为 w 的边放进矩阵一次矩阵乘法似乎走了 w 天那矩阵幂的语义就乱了A^k 到底是“经过 k 天”还是“经过 k 条边”解决办法是把“还在路上”的天数也变成状态。因为 w 不超过 5所以每个城市最多需要 4 个“在路上”的中间状态加上“已经到达”的状态一共 5 个。我习惯把一个城市 v 拆成 v_0, v_1, v_2, v_3, v_4含义如下v_0第 T 天结束时已经真正到达城市 v。v_jj 0正在前往城市 v 的路上距离到达 v 还需要 j 天。注意这里 v_0 是“到达状态”不是“在该城市等待”。每天必须沿着道路前进所以到达 v 后下一天只能从 v_0 走原图出边去下一个城市不能原地休息。3.2 状态之间的转移边我们要构造一个规模为 5n 的矩阵矩阵里保存的是“从行状态经过一天到列状态的最大收益”。先处理原图边。对每条有向边 u - v边权为 w我们在矩阵里加一条u_0 - v_{w-1}权值为 val[v]。为什么目标是 v_{w-1}因为从 u_0 出发那天算第 1 天走完这条 w 天的边还需要 w-1 天才能到达 v。于是把状态放在“距离到达 v 还有 w-1 天”的位置然后通过内部倒计时状态一步步推进到 v_0。再处理每个城市的内部倒计时边。对任意城市 v对 j 1, 2, 3, 4加v_j - v_{j-1}权值为 0。这条边表示“在路上又过了一天”。它把 v_3 推到 v_2把 v_2 推到 v_1把 v_1 推到 v_0。到了 v_0才算真正到达 v。这里有一个容易误解的点val[v] 是在 u_0 - v_{w-1} 那条边加的不是等真正到 v_0 才加。从总收益角度看没有问题因为只要最终走到 v_0val[v] 一定只算一次提前加不会影响整体路径收益。但如果你的实现把 val[v] 放在 v_1 - v_0 上也可以只是要保证所有到达 v 的路径都经过那条边。如果 w 1则 u_0 - v_0权值 val[v]。这时一天内从 u 到 v直接进入 v_0语义和原题完全一致。3.3 初始向量与答案状态初始时第 0 天在 1 号城市已经拿到 val[1]所以向量只在 1_0 位置是 val[1]其他位置都是负无穷。之后的每一步向量与矩阵相乘表示时间增加一天。走完 T 天后答案必须取 1_0 位置的值。因为题目要求在“第 T 天结束时在城市 1”而不是在路上。如果答案位置是负无穷说明不存在合法路径输出 -1。注意这里所有“负无穷”都必须用一个足够小、而且加一个普通数值后仍不会溢出的常量。我习惯用 -(1LL 62)因为最大收益可能接近 1e18如果只用 -(160) 这种量级某些极端情况下加法会出问题。3.4 矩阵大小和稀疏性n 最大 50拆点后状态数是 5n 250。矩阵大小是 250 × 250。这个规模对快速幂来说不算小但完全可以接受。矩阵里大部分位置是负无穷因为真正的转移只有两类原图边和城市内部的倒计时边。所以初始矩阵是稀疏的。快速幂预处理过程中矩阵会逐渐变密但 250 的规模配上 max-plus 乘法预处理 30 次矩阵乘矩阵在 O2 优化的 C 下是可行的。4. 美食节把特殊事件插进连续时间轴4.1 美食节的本质是“单点加值”美食节事件不是新的图结构而是对时间轴的修改。矩阵快速幂只能连续地推进时间但它本身不知道哪一天有特殊事件。我们可以把整个时间轴看成若干段第 0 天到第 t_1 天是一段第 t_1 天到第 t_2 天是一段依此类推。每段内部没有事件可以直接用矩阵快速幂跳过去。到了第 t_i 天我们先保证向量已经推进到这一天的状态然后对向量里城市 c_i 的“到达状态”加 y_i。这个操作的本质是在已经算好的“第 t_i 天各城市状态最大值”上把 c_i 所在位置的值额外加 y_i。因为美食节只在“当天结束时处于该城市”时触发而“处于该城市”对应的状态正是 c_i_0。4.2 分段倍增的实现顺序把所有事件按 t 从小到大排序然后这样处理当前已推进到的天数 cur 初始为 0。对每个事件或每组同时间事件先令 step t_i - cur把向量乘以矩阵的 step 次幂让向量来到第 t_i 天。在向量中给对应城市的 v_0 状态加 y_i。更新时间 cur t_i。所有事件处理完后再把向量乘以矩阵的 T - cur 次幂最终取 1_0 位置。实现时一定要“先乘后加”。因为美食节的额外收益只影响当天之后的状态不影响当天之前的状态。如果先加再乘等于把美食节的收益提前施加到了之前几天答案就会错。4.3 同一天多个事件怎么处理如果同一天有多个美食节我的建议是分组处理把相同 t 的事件放在一组先统一推进到这一天然后把这组事件全部加完再进入下一段时间。分组的好处是避免“同一天事件之间出现 step 0 的乘法”。虽然 step 0 时乘以单位矩阵也不会出错但分组后逻辑更清晰也更容易排查 bug。如果同一天有两个事件在城市 a 和 b直接分别给 a_0 和 b_0 加值即可。它们的贡献不会互相污染因为向量保存的是“每个状态分别的最优值”。如果同一个城市同一天有两个事件那就直接累加。4.4 一个特别容易翻车的点不可达状态加值给 v_0 加 y 之前必须判断这个状态是否可达。如果 dp[v_0] 本身就是负无穷说明没有任何合法路径能让你在第 t_i 天到达 v这时就算加了 y它依然不可达而且不能让它参与后续转移。所以我每次加值前都会判断if (dp[s] ! NEG) dp[s] y;如果不判断负无穷加上 y 仍然是一个很大的负数后续乘矩阵时可能被当作“可达状态”使用导致答案全部变成负无穷或者出现错误的非负路径。这个 bug 非常隐蔽逻辑上很难一眼看出来。5. 代码实现与踩坑记录5.1 一份可复现的 C17 参考实现下面这份代码是我按“拆点 max-plus 事件排序”的思路写的删掉了和题目无关的调试输出可以直接照着理解或改成自己的风格。#include bits/stdc.h using namespace std; const long long NEG -(1LL 62); const int P 5; int n, m, k; long long T; int id(int city, int wait) { return city * P wait; } struct Matrix { int n; vectorvectorlong long a; Matrix(int n 0) : n(n), a(n, vectorlong long(n, NEG)) {} }; Matrix mulMatrix(const Matrix A, const Matrix B) { int n A.n; Matrix C(n); for (int i 0; i n; i) { for (int mid 0; mid n; mid) { if (A.a[i][mid] NEG) continue; for (int j 0; j n; j) { if (B.a[mid][j] NEG) continue; C.a[i][j] max(C.a[i][j], A.a[i][mid] B.a[mid][j]); } } } return C; } vectorlong long mulVectorMatrix(const Matrix A, const vectorlong long vec) { int n A.n; vectorlong long res(n, NEG); for (int i 0; i n; i) { if (vec[i] NEG) continue; for (int j 0; j n; j) { if (A.a[i][j] NEG) continue; res[j] max(res[j], vec[i] A.a[i][j]); } } return res; } struct Event { long long t; int city; long long y; bool operator (const Event other) const { return t other.t; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m T k; vectorlong long val(n); for (int i 0; i n; i) cin val[i]; vectorarrayint,3 edges(m); for (int i 0; i m; i) { int u, v, w; cin u v w; --u; --v; edges[i] {u, v, w}; } vectorEvent events(k); for (int i 0; i k; i) { long long t, y; int c; cin t c y; --c; events[i] {t, c, y}; } sort(events.begin(), events.end()); int N n * P; Matrix base(N); for (auto [u, v, w] : edges) { int from id(u, 0); int to id(v, w - 1); base.a[from][to] max(base.a[from][to], val[v]); } for (int v 0; v n; v) { for (int j 1; j 4; j) { int from id(v, j); int to id(v, j - 1); base.a[from][to] max(base.a[from][to], 0LL); } } vectorMatrix pw; pw.push_back(base); while ((1LL pw.size()) T) { pw.push_back(mulMatrix(pw.back(), pw.back())); } auto apply [](vectorlong long vec, long long len) { int b 0; while (len 0) { if (len 1LL) { vec mulVectorMatrix(pw[b], vec); } len 1LL; b; } }; vectorlong long dp(N, NEG); dp[id(0, 0)] val[0]; long long cur 0; for (int i 0; i k; ) { long long t events[i].t; apply(dp, t - cur); while (i k events[i].t t) { int s id(events[i].city, 0); if (dp[s] ! NEG) dp[s] events[i].y; i; } cur t; } apply(dp, T - cur); long long ans dp[id(0, 0)]; if (ans NEG / 2) cout -1 \n; else cout ans \n; return 0; }这份代码里apply函数是核心它不会真的去乘一个巨大的 T 次方而是把 len 拆成二进制位每次用预处理好的 pw[b] 去乘向量。因为向量乘矩阵的复杂度是 O(N^2)所以每个时间段只需要 O(N^2 log T)而不是每次都重新做矩阵乘矩阵。5.2 复杂度分析状态数 N 5n。预处理快速幂需要做 O(log T) 次矩阵乘矩阵每次 O(N^3)。k 个美食节每个时间段做 O(log T) 次向量乘矩阵每次 O(N^2)。总复杂度大约是O(N^3 log T kN^2 log T)对于 N 250log T 约 30这个复杂度是能接受的。预处理矩阵乘矩阵那一步最重所以矩阵乘法里跳过了所有负无穷位置实际运行会快不少。5.3 我实际交题时踩过的三个坑第一个坑矩阵乘法方向写反。我一开始把mulVectorMatrix写成了“枚举列向量”的写法结果答案一直不对。后来我固定一个原则dp 是行向量结果的下标是目标状态。所以就是res[j] max(res[j], vec[i] A.a[i][j])。第二个坑美食节事件加值前没有判负无穷。这个问题在数据小的时候不明显因为负无穷加上一个很大的 y 可能仍然小于正解但某些路径恰好需要这个“假可达”状态就会把答案带偏。后来统一改成判断dp[s] ! NEG才加再也没出过问题。第三个坑没有分组处理同一天的事件。我最初把每个事件独立排序一个个处理结果两个同一天不同城市的事件之间出现了apply(dp, 0)。我的apply函数里len 0时不会乘任何矩阵看起来没问题但如果其中一个事件加值后不小心被另一个事件的相同城市状态覆盖逻辑就会混乱。改成按 t 分组后整个时间轴就清晰了。6. 常见问题速查现象原因处理方法最终答案一直是负无穷矩阵里漏了内部倒计时边 v_j - v_{j-1}检查每个城市的 j 1..4 的内部转移边权为 1 的城市收益不对原图边 u_0 - v_0 的权没写成 val[v]确认 w - 1 0 时目标状态是 v_0美食节加值后答案变大先加后乘把额外收益往前传播了每个时间段先 apply 再加值同一天多个事件互相影响没有分组处理事件间出现了无意义的矩阵乘法按 t 分组整组加完再进入下一段矩阵乘法溢出NEG 不够小或者负无穷参与了加法用 -(1LL 62)加值前判断不可达只过了小数据大数据 TLE每个事件都在做矩阵乘矩阵预处理矩阵幂事件段只做向量乘矩阵做这类题我的个人体会是不要把美食节当成一个“特殊技巧”它本质上就是在连续转移的中间插了几个单点修改。你只要把时间轴切好矩阵快速幂和事件修改就能各司其职。最后再分享一个调试小技巧如果样例没过先不要急着盯矩阵里的数字。写一个朴素 O(T * m) 的 DP把 T 设成一个小值跑同一个随机小数据然后对比朴素 DP 和矩阵乘法在每个时间点的状态值。哪一天开始不一致问题就出在哪一段转移上。这个“对拍”习惯能帮你省下大量在矩阵乘法里逐行排查的时间。 
长河君 · 2026/10/14 10:05:35 · 阅读 1.2k 矩阵快速幂优化DP：NOI2020美食家拆点建模全解析
看到 [NOI2020]美食家 这个标题我的第一反应是这不是一道签到题而是一道非常典型的“DP 思路一眼就能看出来但数据范围逼着你必须上矩阵快速幂”的题。它把图上带权最长路、恰好 T 天、节点重复收益、单点事件加成四个要素揉在一起看起来像图论做起来像线性代数最后还夹带一点“事件排序”的工程感。适合正在备战竞赛、想系统学矩阵快速幂优化 DP 的同学反复咀嚼。我第一次做的时候拆点那一步卡了很久后来想明白“状态里必须保留天数余量”这件事整个题才豁然开朗。1. 这道题到底在问什么1.1 题面还原与关键信息整理题面可以压缩成这样一个模型有 n 个城市m 条单向道路每条道路有一个耗时 w范围是 1 到 5。你从 1 号城市出发要在第 T 天回到 1 号城市。每到达一个城市包括第 0 天所在的 1 号城市你会获得这个城市的美食愉悦值同一个城市多次到达愉悦值可以重复获得。除了这些基础收益还有 k 个“美食节”事件每个事件描述为在第 t_i 天如果当天结束时你在城市 c_i那么可以额外获得 y_i 愉悦值。最后要求的是“恰好第 T 天在城市 1”时的最大愉悦值如果无法做到输出 -1。这个题最迷惑人的地方是“恰好 T 天”。它意味着不能简单跑一个最长路因为最长路不会限定步数但也不能直接枚举天数因为 T 可以给到 1e9 的级别。你要找的本质上是一条“长度为 T 的路径”同时路径上每个节点的权值可以累积并且某些精确时间点上有额外奖励。1.2 数据范围决定了算法方向n 只有 50 左右m 也在 500 以下但 T 是 1e9 级别。这个数据范围组合非常明显图很小时间很长适合把“图上的状态转移”变成“矩阵的幂”。如果把每天当成一次转移那么朴素 DP 的复杂度是 O(T * m)T 一旦到 1e9 就完全不可行。但如果我们能构造出一个“转移一天”的矩阵那么连续走 T 天就等价于把这个矩阵乘 T 次。矩阵快速幂可以把 T 次压缩到 log T 次问题就转化为怎么把原题的天数转移写成一个矩阵并且让这个矩阵支持快速幂。这里有一个隐藏前提普通矩阵乘法只能处理“每次转移时间和权重都固定”的递推。原题的边权 w 不是 1所以走一条 w 天的边不能简单作为一步转移。于是就需要拆点。1.3 先给结论算法主线整道题的主线可以分成四步先写朴素 DP确认状态和转移是对的。把每个城市拆成 5 个状态用来表示“正在前往该城市的路上还剩几天”。用 max-plus 矩阵乘法代替普通矩阵乘法构造“一天转移矩阵”。把美食节事件按时间排序每两个事件之间用矩阵快速幂跳过去到点再单点加值。后面的所有内容都是围绕这四步展开的。2. 从朴素 DP 到矩阵快速幂2.1 最容易想到的 f[i][u]不考虑美食节时朴素 DP 是很好想的。设 f[i][u] 表示第 i 天结束时在城市 u 的最大愉悦值。初始化 f[0][1] val[1]。转移时枚举每条边 u - v边权为 wf[i w][v] max(f[i w][v], f[i][u] val[v])这个转移的意思很直白如果你第 i 天在 u走一条 w 天的路那么第 i w 天到达 v并获得 v 的愉悦值。这个 DP 的正确性没有问题问题在于 i 的范围太大。T 是 1e9哪怕 n 再小也没法真的开一个 1e9 的数组更不可能做 1e9 次转移。2.2 把 DP 写成向量和矩阵观察上面的转移它本质上是当前第 i 天的状态只决定第 i w 天的状态而且状态之间是“取最大值”的递推。如果能设计出一种“每次只前进一天”的转移那么就可以写成vector_i vector_{i-1} × Matrix其中 vector_i 是一个长度为 N 的向量N 是所有状态的数量。Matrix 的第 j 行第 k 列表示“从状态 j 经过一天到达状态 k 能获得的收益”。这里的关键是“经过一天”而不是“经过 w 天”。只要 Matrix 能完成“一天一天地推进”那么走 T 天就是 vector_0 乘以 Matrix 的 T 次方。2.3 max-plus 矩阵乘法是什么普通矩阵乘法里C[i][j] sum_k A[i][k] * B[k][j]。但我们要的转移是“取最大值”而不是“求和”所以需要换成 max-plus 乘法C[i][j] max_k (A[i][k] B[k][j])这个公式里原来的“乘法”变成了“加法”原来的“加法”变成了“取 max”。名字里的 max-plus 就是这么来的。为什么可以用它因为我们需要求的是路径收益的最大值而两条路径拼接时总收益等于两段收益相加。如果用普通矩阵乘法会把所有路径收益加起来那求的是路径数量或者某种和不是最大值。max-plus 矩阵乘法仍然满足结合律所以快速幂照样能用。这一点非常重要。快速幂依赖的核心性质就是结合律而不是普通乘法里的“乘加”结构。只要矩阵乘法满足结合律就能用倍增的方式预处理幂次。提示第一次接触 max-plus 时别把它想得太神秘。它只是把“状态可达性”从布尔矩阵换成了“最大收益”矩阵。矩阵的 k 次幂的第 i 行第 j 列含义是从状态 i 出发恰好走 k 步到达状态 j 能获得的最大收益。3. 拆点建模的完整细节3.1 为什么必须拆点普通矩阵快速幂每次只推进一天但原题边权 w 最大是 5。如果直接把边权为 w 的边放进矩阵一次矩阵乘法似乎走了 w 天那矩阵幂的语义就乱了A^k 到底是“经过 k 天”还是“经过 k 条边”解决办法是把“还在路上”的天数也变成状态。因为 w 不超过 5所以每个城市最多需要 4 个“在路上”的中间状态加上“已经到达”的状态一共 5 个。我习惯把一个城市 v 拆成 v_0, v_1, v_2, v_3, v_4含义如下v_0第 T 天结束时已经真正到达城市 v。v_jj 0正在前往城市 v 的路上距离到达 v 还需要 j 天。注意这里 v_0 是“到达状态”不是“在该城市等待”。每天必须沿着道路前进所以到达 v 后下一天只能从 v_0 走原图出边去下一个城市不能原地休息。3.2 状态之间的转移边我们要构造一个规模为 5n 的矩阵矩阵里保存的是“从行状态经过一天到列状态的最大收益”。先处理原图边。对每条有向边 u - v边权为 w我们在矩阵里加一条u_0 - v_{w-1}权值为 val[v]。为什么目标是 v_{w-1}因为从 u_0 出发那天算第 1 天走完这条 w 天的边还需要 w-1 天才能到达 v。于是把状态放在“距离到达 v 还有 w-1 天”的位置然后通过内部倒计时状态一步步推进到 v_0。再处理每个城市的内部倒计时边。对任意城市 v对 j 1, 2, 3, 4加v_j - v_{j-1}权值为 0。这条边表示“在路上又过了一天”。它把 v_3 推到 v_2把 v_2 推到 v_1把 v_1 推到 v_0。到了 v_0才算真正到达 v。这里有一个容易误解的点val[v] 是在 u_0 - v_{w-1} 那条边加的不是等真正到 v_0 才加。从总收益角度看没有问题因为只要最终走到 v_0val[v] 一定只算一次提前加不会影响整体路径收益。但如果你的实现把 val[v] 放在 v_1 - v_0 上也可以只是要保证所有到达 v 的路径都经过那条边。如果 w 1则 u_0 - v_0权值 val[v]。这时一天内从 u 到 v直接进入 v_0语义和原题完全一致。3.3 初始向量与答案状态初始时第 0 天在 1 号城市已经拿到 val[1]所以向量只在 1_0 位置是 val[1]其他位置都是负无穷。之后的每一步向量与矩阵相乘表示时间增加一天。走完 T 天后答案必须取 1_0 位置的值。因为题目要求在“第 T 天结束时在城市 1”而不是在路上。如果答案位置是负无穷说明不存在合法路径输出 -1。注意这里所有“负无穷”都必须用一个足够小、而且加一个普通数值后仍不会溢出的常量。我习惯用 -(1LL 62)因为最大收益可能接近 1e18如果只用 -(160) 这种量级某些极端情况下加法会出问题。3.4 矩阵大小和稀疏性n 最大 50拆点后状态数是 5n 250。矩阵大小是 250 × 250。这个规模对快速幂来说不算小但完全可以接受。矩阵里大部分位置是负无穷因为真正的转移只有两类原图边和城市内部的倒计时边。所以初始矩阵是稀疏的。快速幂预处理过程中矩阵会逐渐变密但 250 的规模配上 max-plus 乘法预处理 30 次矩阵乘矩阵在 O2 优化的 C 下是可行的。4. 美食节把特殊事件插进连续时间轴4.1 美食节的本质是“单点加值”美食节事件不是新的图结构而是对时间轴的修改。矩阵快速幂只能连续地推进时间但它本身不知道哪一天有特殊事件。我们可以把整个时间轴看成若干段第 0 天到第 t_1 天是一段第 t_1 天到第 t_2 天是一段依此类推。每段内部没有事件可以直接用矩阵快速幂跳过去。到了第 t_i 天我们先保证向量已经推进到这一天的状态然后对向量里城市 c_i 的“到达状态”加 y_i。这个操作的本质是在已经算好的“第 t_i 天各城市状态最大值”上把 c_i 所在位置的值额外加 y_i。因为美食节只在“当天结束时处于该城市”时触发而“处于该城市”对应的状态正是 c_i_0。4.2 分段倍增的实现顺序把所有事件按 t 从小到大排序然后这样处理当前已推进到的天数 cur 初始为 0。对每个事件或每组同时间事件先令 step t_i - cur把向量乘以矩阵的 step 次幂让向量来到第 t_i 天。在向量中给对应城市的 v_0 状态加 y_i。更新时间 cur t_i。所有事件处理完后再把向量乘以矩阵的 T - cur 次幂最终取 1_0 位置。实现时一定要“先乘后加”。因为美食节的额外收益只影响当天之后的状态不影响当天之前的状态。如果先加再乘等于把美食节的收益提前施加到了之前几天答案就会错。4.3 同一天多个事件怎么处理如果同一天有多个美食节我的建议是分组处理把相同 t 的事件放在一组先统一推进到这一天然后把这组事件全部加完再进入下一段时间。分组的好处是避免“同一天事件之间出现 step 0 的乘法”。虽然 step 0 时乘以单位矩阵也不会出错但分组后逻辑更清晰也更容易排查 bug。如果同一天有两个事件在城市 a 和 b直接分别给 a_0 和 b_0 加值即可。它们的贡献不会互相污染因为向量保存的是“每个状态分别的最优值”。如果同一个城市同一天有两个事件那就直接累加。4.4 一个特别容易翻车的点不可达状态加值给 v_0 加 y 之前必须判断这个状态是否可达。如果 dp[v_0] 本身就是负无穷说明没有任何合法路径能让你在第 t_i 天到达 v这时就算加了 y它依然不可达而且不能让它参与后续转移。所以我每次加值前都会判断if (dp[s] ! NEG) dp[s] y;如果不判断负无穷加上 y 仍然是一个很大的负数后续乘矩阵时可能被当作“可达状态”使用导致答案全部变成负无穷或者出现错误的非负路径。这个 bug 非常隐蔽逻辑上很难一眼看出来。5. 代码实现与踩坑记录5.1 一份可复现的 C17 参考实现下面这份代码是我按“拆点 max-plus 事件排序”的思路写的删掉了和题目无关的调试输出可以直接照着理解或改成自己的风格。#include bits/stdc.h using namespace std; const long long NEG -(1LL 62); const int P 5; int n, m, k; long long T; int id(int city, int wait) { return city * P wait; } struct Matrix { int n; vectorvectorlong long a; Matrix(int n 0) : n(n), a(n, vectorlong long(n, NEG)) {} }; Matrix mulMatrix(const Matrix A, const Matrix B) { int n A.n; Matrix C(n); for (int i 0; i n; i) { for (int mid 0; mid n; mid) { if (A.a[i][mid] NEG) continue; for (int j 0; j n; j) { if (B.a[mid][j] NEG) continue; C.a[i][j] max(C.a[i][j], A.a[i][mid] B.a[mid][j]); } } } return C; } vectorlong long mulVectorMatrix(const Matrix A, const vectorlong long vec) { int n A.n; vectorlong long res(n, NEG); for (int i 0; i n; i) { if (vec[i] NEG) continue; for (int j 0; j n; j) { if (A.a[i][j] NEG) continue; res[j] max(res[j], vec[i] A.a[i][j]); } } return res; } struct Event { long long t; int city; long long y; bool operator (const Event other) const { return t other.t; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m T k; vectorlong long val(n); for (int i 0; i n; i) cin val[i]; vectorarrayint,3 edges(m); for (int i 0; i m; i) { int u, v, w; cin u v w; --u; --v; edges[i] {u, v, w}; } vectorEvent events(k); for (int i 0; i k; i) { long long t, y; int c; cin t c y; --c; events[i] {t, c, y}; } sort(events.begin(), events.end()); int N n * P; Matrix base(N); for (auto [u, v, w] : edges) { int from id(u, 0); int to id(v, w - 1); base.a[from][to] max(base.a[from][to], val[v]); } for (int v 0; v n; v) { for (int j 1; j 4; j) { int from id(v, j); int to id(v, j - 1); base.a[from][to] max(base.a[from][to], 0LL); } } vectorMatrix pw; pw.push_back(base); while ((1LL pw.size()) T) { pw.push_back(mulMatrix(pw.back(), pw.back())); } auto apply [](vectorlong long vec, long long len) { int b 0; while (len 0) { if (len 1LL) { vec mulVectorMatrix(pw[b], vec); } len 1LL; b; } }; vectorlong long dp(N, NEG); dp[id(0, 0)] val[0]; long long cur 0; for (int i 0; i k; ) { long long t events[i].t; apply(dp, t - cur); while (i k events[i].t t) { int s id(events[i].city, 0); if (dp[s] ! NEG) dp[s] events[i].y; i; } cur t; } apply(dp, T - cur); long long ans dp[id(0, 0)]; if (ans NEG / 2) cout -1 \n; else cout ans \n; return 0; }这份代码里apply函数是核心它不会真的去乘一个巨大的 T 次方而是把 len 拆成二进制位每次用预处理好的 pw[b] 去乘向量。因为向量乘矩阵的复杂度是 O(N^2)所以每个时间段只需要 O(N^2 log T)而不是每次都重新做矩阵乘矩阵。5.2 复杂度分析状态数 N 5n。预处理快速幂需要做 O(log T) 次矩阵乘矩阵每次 O(N^3)。k 个美食节每个时间段做 O(log T) 次向量乘矩阵每次 O(N^2)。总复杂度大约是O(N^3 log T kN^2 log T)对于 N 250log T 约 30这个复杂度是能接受的。预处理矩阵乘矩阵那一步最重所以矩阵乘法里跳过了所有负无穷位置实际运行会快不少。5.3 我实际交题时踩过的三个坑第一个坑矩阵乘法方向写反。我一开始把mulVectorMatrix写成了“枚举列向量”的写法结果答案一直不对。后来我固定一个原则dp 是行向量结果的下标是目标状态。所以就是res[j] max(res[j], vec[i] A.a[i][j])。第二个坑美食节事件加值前没有判负无穷。这个问题在数据小的时候不明显因为负无穷加上一个很大的 y 可能仍然小于正解但某些路径恰好需要这个“假可达”状态就会把答案带偏。后来统一改成判断dp[s] ! NEG才加再也没出过问题。第三个坑没有分组处理同一天的事件。我最初把每个事件独立排序一个个处理结果两个同一天不同城市的事件之间出现了apply(dp, 0)。我的apply函数里len 0时不会乘任何矩阵看起来没问题但如果其中一个事件加值后不小心被另一个事件的相同城市状态覆盖逻辑就会混乱。改成按 t 分组后整个时间轴就清晰了。6. 常见问题速查现象原因处理方法最终答案一直是负无穷矩阵里漏了内部倒计时边 v_j - v_{j-1}检查每个城市的 j 1..4 的内部转移边权为 1 的城市收益不对原图边 u_0 - v_0 的权没写成 val[v]确认 w - 1 0 时目标状态是 v_0美食节加值后答案变大先加后乘把额外收益往前传播了每个时间段先 apply 再加值同一天多个事件互相影响没有分组处理事件间出现了无意义的矩阵乘法按 t 分组整组加完再进入下一段矩阵乘法溢出NEG 不够小或者负无穷参与了加法用 -(1LL 62)加值前判断不可达只过了小数据大数据 TLE每个事件都在做矩阵乘矩阵预处理矩阵幂事件段只做向量乘矩阵做这类题我的个人体会是不要把美食节当成一个“特殊技巧”它本质上就是在连续转移的中间插了几个单点修改。你只要把时间轴切好矩阵快速幂和事件修改就能各司其职。最后再分享一个调试小技巧如果样例没过先不要急着盯矩阵里的数字。写一个朴素 O(T * m) 的 DP把 T 设成一个小值跑同一个随机小数据然后对比朴素 DP 和矩阵乘法在每个时间点的状态值。哪一天开始不一致问题就出在哪一段转移上。这个“对拍”习惯能帮你省下大量在矩阵乘法里逐行排查的时间。