有些事必须按顺序做：先和面才能擀皮，先擀皮才能包饺子。把每件事看成一个点，把“A 必须在 B 之前完成”看成一条有向边 A→B，整张图就必须无环——有环意味着“A 在 B 前”和“B 在 A 前”同时成立，这要求本身自相矛盾。
无环的有向图叫 DAG。把 DAG 的所有点排成一列，使每条边都从前指向后，这个排列就叫拓扑序。拓扑排序本身不是目的，它的价值是：把 DAG 变成一条可以从左往右扫的序列——扫到某个点时，它的所有前驱都已经处理完了。于是“必须先算谁”这个依赖问题被彻底消掉，剩下的事就是在一条链上做 DP。
| 问法 | 在拓扑序上做什么 | 复杂度 |
|---|---|---|
| 有没有环 | 数出队点数 cnt 是否等于 n | O(n + m) |
| 最早完成时间 / 最长路 | f[v] = max(f[v], f[u] + w) | O(n + m) |
| 路径条数 / 方案数 | f[v] += f[u]，源点置 1 | O(n + m) |
| 字典序最小的拓扑序 | 把 queue 换成小根堆 | O((n + m) log n) |
| DAG 上最短路（可有负权） | f[v] = min(f[v], f[u] + w) | O(n + m) |
三块骨头：入度表 + Kahn 算法（求出拓扑序、顺带判环）、小根堆（把拓扑序压成字典序最小）、拓扑序上的 DP（在出队时把信息往后推）。第三块是这一节真正的重点，前两块是把图变成序列的工具。
| 组成 | 含义 / 格式要求 |
|---|---|
in[v] | v 的入度 = 有多少条边指向 v = 还有多少个前驱没处理。每读一条边 u→v 就 ++in[v]。 |
in[i] == 0 的点 | 没有任何前驱，第一步就能做。它们是拓扑序的“第一层”，必须全部入队——漏一个就少一串点。 |
queue | 存“前驱都已完成、但还没输出”的点。用 queue、stack、priority_queue 都合法，区别只在得到哪一个拓扑序。 |
--in[v] == 0 | u 出队意味着 u 已完成，v 少了一个未完成的前驱。减到 0 说明 v 的前驱全齐了，可以入队。 |
必须先减再判 | 写成 in[v] == 0（忘了自减）→ v 永远不入队，算法只输出第一层；写成 in[v]-- > 0 → 入队时机全部推迟一层。两种都不报错，只是答案错。 |
cnt | 出队的点数。cnt == n 说明所有点都被排进了序列；cnt < n 说明剩下的点互相牵制，它们一定落在某个环上。 |
为什么 cnt < n 就是有环 | 环上每个点的入度里至少有一条来自环内，永远不会减到 0；反之无环时总能不断找到入度为 0 的点（证明见数学补给）。 |
复杂度 | 每个点入队出队各一次，每条边被看一次：O(n + m)。m = 5×10⁵ 也就几毫秒。 |
自环 | u→u 让 in[u] ≥ 1，u 永远进不了队列，最终 cnt < n → 判成有环。这个结论是对的。 |
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
vector<int> g[N]; // g[u]：u 的所有后继
int in[N];
void add(int u, int v) { g[u].push_back(v); ++in[v]; }
int main() {
add(1, 2); add(1, 3); add(2, 4); add(3, 4); add(4, 5);
queue<int> q;
for (int i = 1; i <= 5; ++i)
if (in[i] == 0) q.push(i); // 只有 1 号没有前驱
int cnt = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
cout << u << ' '; // 出队即输出，天然是一个拓扑序
++cnt;
for (int v : g[u])
if (--in[v] == 0) q.push(v);
}
cout << "\n" << cnt << "\n"; // 1 2 3 4 5 / 5
return 0;
}拓扑序一般不唯一：本例 2 和 3 的顺序可以互换，queue 的先来先服务决定了你拿到哪一个。
要保存拓扑序就开一个 ord[]，在 ++cnt 的地方写 ord[cnt] = u。后面做 DP 时直接扫 ord 也行，边扫边推也行。
| 组成 | 含义 / 格式要求 |
|---|---|
priority_queue<int, vector<int>, greater<int>> | 小根堆。三个模板参数依次是元素类型、底层容器、比较器。 |
greater<int> | 比较器：greater(a,b) 表示 a 的优先级比 b 低，所以堆顶是最小的那个。默认的 less<int> 堆顶是最大值。 |
为什么换成它就能字典序最小 | queue 是先进先出，谁先入队谁先出（跟编号无关）；小根堆每次弹“当前所有可选项里编号最小”的那个。 |
正确性（交换论证） | 设当前可选取集合是 S，其中最小的是 x。任何一个合法拓扑序的这一位若不是 x，就把它挪到这里并把 x 提前：x 此刻没有未完成的前驱，前移不会违反任何约束，其余点相对顺序不变，字典序只会变小。所以每次取最小不吃亏。 |
复杂度 | n 次入堆、n 次出堆，每次 O(log n)；每条边看一次。总计 O((n + m) log n)，n = 10⁵ 也轻松。 |
和 sort 的 cmp 方向相反 | sort 的 cmp 返回 true 表示 a 排在 b 前面；堆的比较器返回 true 表示 a 的优先级更低。写反了就变成大根堆。 |
换自定义类型 | 要按多个关键字排时，写一个重载了 operator() 的结构体当第三个参数；元素是 int 时无需定义结构体。 |
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
vector<int> g[N];
int in[N];
void add(int u, int v) { g[u].push_back(v); ++in[v]; }
int main() {
add(1, 3); add(1, 2); // 注意：3 先入队
add(2, 4); add(3, 4); add(4, 5);
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i <= 5; ++i)
if (in[i] == 0) pq.push(i);
while (!pq.empty()) {
int u = pq.top(); pq.pop();
cout << u << ' ';
for (int v : g[u])
if (--in[v] == 0) pq.push(v);
}
cout << "\n"; // 1 2 3 4 5（用 queue 会得到 1 3 2 4 5）
return 0;
}“字典序最小”指整个序列按位比较最小，不是“编号 1 尽量靠前、再让 2 尽量靠前”。这两个目标不是一回事，遇到“让 1 最早、再让 2 最早”的问法，小根堆正着贪心不一定对，要另想办法。
priority_queue 不支持遍历和删除任意元素，需要时改用 multiset 或手写堆。
| 组成 | 含义 / 格式要求 |
|---|---|
为什么 DAG 上能 DP | 拓扑序保证所有能到达 v 的点都排在 v 之前，算出队到 v 时，它需要的所有 f 值都已经定稿。这就是“无后效性”的具体形态。 |
和 Dijkstra 的区别 | DAG 上不需要优先队列：拓扑序本身就是正确的松弛顺序，O(n + m)，而且负权也照样正确。 |
更新时机 | 必须在 --in[v] == 0 判定的前面。那条边无论 v 是否刚好可以入队，都要贡献一次。写在 if 里面就漏了。 |
最长路取 max | f[v] 表示“到 v 为止的最优值”，每来一个前驱就试着用它更新一次。初值按题意定：−∞、0，或“自己的耗时”。 |
方案数用加法 | f[v] = Σ f[p]（对所有边 p→v）。源点置 1，其余置 0；每次加法后立刻 % MOD，别攒到最后。 |
多个源点 | 入度为 0 的点全都是源点。判题时要按题意决定“全部当起点”还是“只认某一个源点，其余置无效值”。 |
出边时加自己 | 没有边权、只有点权时，写成 f[v] = max(f[v], f[u] + t[v])，把“自己的耗时”放在出边这一步加，源点只需初值 f[i] = t[i]。 |
反向图 | 递推方向反了（要的是“从 v 出发”的值）就把图反向存一遍再拓扑排序，不要试图倒着扫拓扑序——倒序扫只对“所有前驱值已知”有效。 |
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
vector<int> g[N];
int in[N], t[N] = {0, 5, 3, 2, 4, 1}, f[N];
void add(int u, int v) { g[u].push_back(v); ++in[v]; }
int main() {
add(1, 2); add(1, 3); add(2, 4); add(3, 4); add(4, 5);
queue<int> q;
for (int i = 1; i <= 5; ++i) {
f[i] = t[i]; // 初值：只做自己
if (in[i] == 0) q.push(i);
}
int ans = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
ans = max(ans, f[u]);
for (int v : g[u]) {
f[v] = max(f[v], f[u] + t[v]); // v 要等所有前驱，取最晚的那个
if (--in[v] == 0) q.push(v);
}
}
cout << ans << "\n"; // 13：串行是 15，并行省了 2
return 0;
}f 的初值决定一切：最长路用 −∞ 或“自己的耗时”，方案数用 0/1。写错初值不会崩，只会安静地输出错数。
把更新写进 if (--in[v] == 0) 的大括号里是本节最高频的错法：只有“最后一个前驱”的那次更新生效，f[v] 变成“最后一个前驱的答案”而不是“所有前驱的最大值”。
有 n 项杂务要完成，每项杂务需要一定的时间。杂务之间有先后关系：某些杂务必须在另一些杂务完成之后才能开始。
不违反先后关系的多个杂务可以同时进行，人手不限。求完成全部杂务所需的最短时间。
输入格式：第一行一个整数 n（n ≤ 10000）。
接下来 n 行，每行描述一项杂务：第一个数是杂务编号 i，第二个数是完成它需要的时间 lenᵢ，后面跟着若干整数，是这项杂务的全部前置杂务编号，以 0 结束。
输出格式：一行一个整数，表示完成所有杂务所需的最短时间。
数据保证先后关系不构成环，且每个杂务的时间是不超过 10⁴ 的正整数。
先看一遍题目在问什么。问的是“全部完成的最短时间”，而人手不限，所以限制时间的只有依赖关系：一项杂务不能早于它所有前置杂务的最晚完成时间开始。
状态。令 f[u] 表示杂务 u 的最早完成时刻（从 0 时刻开始计时）。它只可能由两件事决定：自己的耗时 len[u]，以及所有前置杂务里完成得最晚的那一个。
f[u] = len[u] + max{ f[p] : p 是 u 的前置杂务 }；没有前置时 f[u] = len[u]。是 max 不是 sum：前置可以并行，u 只需要等最慢的那个，其它人早就做完了。
顺序。f[u] 依赖所有前驱，所以必须按拓扑序算。Kahn 的出队顺序恰好满足“前驱先出”：u 能入队，说明它的入度已经被减到 0，也就是所有前驱都已经出队、f 值定稿。这就是“无后效性”落到代码上的样子。
答案。是所有 f[u] 的最大值，不是 f[n]。可以并行的图里，最后完成的不一定是编号最大的那项杂务。样例分叉成两支、两支又汇合，就是专门用来打这个坑的。
转移怎么写最省事。把初值设成 f[i] = len[i]（“只做自己”），然后在处理边 u→v 时写 f[v] = max(f[v], f[u] + len[v])。因为 len[v] 是常数，它可以从 max 里提出来：max(f[u] + len[v]) = len[v] + max(f[u])，正好是我们要的式子。
复杂度。每个点出队一次、每条边看一次，O(n + m)。n ≤ 10⁴ 时不到 0.1 ms，瓶颈在读入。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
vector<int> g[N]; // g[p] 存 p 的所有后继：p 做完才能做它们
int in[N]; // 入度 = 还有多少个前置杂务没完成
int len[N]; // 每项杂务自己的耗时
int f[N]; // f[u]：u 的最早完成时刻
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int id, t, p;
cin >> id >> t; // 用 id 而不是 i：编号以行首为准更稳
len[id] = t;
while (cin >> p, p) { // 读到 0 为止
g[p].push_back(id); // p 是 id 的前置 → 边 p → id
++in[id]; // id 多了一个前置
}
}
queue<int> q;
for (int i = 1; i <= n; ++i) {
f[i] = len[i]; // 初值：没有前置时，做完自己就完事
if (in[i] == 0) q.push(i); // 没有前置的杂务立刻可以开工
}
int ans = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
ans = max(ans, f[u]); // 每个点都可能是“最后完成的那个”
for (int v : g[u]) {
f[v] = max(f[v], f[u] + len[v]); // v 要等所有前置，取最晚的
if (--in[v] == 0) q.push(v); // 前置全齐，v 可以开工了
}
}
cout << ans << "\n";
return 0;
}| 代码片段 | 含义与理由 |
|---|---|
vector<int> g[N]; int in[N]; | 邻接表存后继，入度数组单独一个。存后继而不是存前驱，是因为 DP 的方向是“从已完成推到未完成”。 |
cin >> id >> t; | 读编号和时间。用编号当下标而不是循环变量 i：题目每行第一个数就是编号，直接用它，行号与编号是否一致就不用关心了。 |
len[id] = t; | 时间跟着编号存。这样后面出边时可以直接用 len[v]，不必再翻回来找。 |
while (cin >> p, p) | 逗号表达式：先执行 cin >> p，再拿 p 当循环条件。读到 0 就停，读入失败也停。 |
g[p].push_back(id); ++in[id]; | 边的方向由“谁必须先完成”决定：前置 p 在后继 id 之前。存反了整个 DP 会倒着算，答案错。 |
f[i] = len[i]; | 初值的含义是“假设没有任何前置”。有了它，转移里就不用再判“有没有前置”。 |
if (in[i] == 0) q.push(i); | 入度为 0 = 没有前置 = 第 0 时刻就能开工。它们全部入队，不是只入一个。 |
ans = max(ans, f[u]); | 答案在这里取最大，而不是取 f[n]。这是本题最容易错的一行。 |
f[v] = max(f[v], f[u] + len[v]); | v 必须等完所有前驱才能开始，所以对每个前驱 u 算一次“等完 u 才开工”的完成时刻，取最大。 |
if (--in[v] == 0) q.push(v); | 这一行和上一行是并列关系，不是包含关系：无论 v 是否入队，上面那句都要执行。 |
while (!q.empty()) | 队列空了但还有点没出队，说明有环。本题保证无环，所以省掉了 cnt 判环；通用模板要留。 |
判环。加一个 cnt，出队时 ++，结束时 if (cnt < n) 就是有环。三行代码，不用额外的数组。
最长路。把 max 留着，把“自己的耗时”换成边权即可。若边权存在结构体里，就写 f[v] = max(f[v], f[u] + e.w)。
方案数。f[v] = (f[v] + f[u]) % MOD，源点 f = 1。注意重边要小心：两条 u→v 的重边代表两条不同的路径，会被加两次，这是对的；但如果题目把重边当成一条，就得先去重。
字典序最小。queue 换小根堆。反过来要字典序最大就换回 priority_queue<int>（默认大根堆）。
DAG 上最短路。把 max 换成 min，初值换成 INF。负权边也照样对，这是它比 Dijkstra 强的地方——Dijkstra 的正确性依赖“边权非负”，拓扑序不依赖。
判环的第二种写法：DFS 三色。白 = 没访问，灰 = 在递归栈里，黑 = 已结束。搜到一个灰点就说明回到了当前路径上，即找到环。优点是能顺手把环上的点输出；缺点是要递归，n = 10⁵ 的链可能爆栈。Kahn 不递归、还免费送你拓扑序，判环首选它。
把 if (--in[v] == 0) 写成 if (in[v] == 0)：入度从不减少，只有第一层能入队 → cnt 极小、答案只有第一层 → WA，而且输出看着“很合理”，最难查。
初始入队写成 for (i = 0; i < n; ++i)：编号是 1..n 的话，这样只扫了 0..n−1，漏掉 n 号点、又凭空多算一个不存在的 0 号点 → WA。下标从 1 开始就必须写 i = 1; i <= n。
边存反了（该 g[v].push_back(u) 却写成 g[u].push_back(v)）：拓扑序整个倒过来 → WA。症状是“样例能过、稍大的数据全挂”，因为对称的图恰好对。
答案取 f[n] 而不是所有 f 的最大值：编号最大的杂务未必最后完成 → WA。
把 DP 更新写进 if (--in[v] == 0) 的括号里：只有最后一个前驱的那次更新生效 → WA，答案恒定偏小，且程序完全正常。
用邻接矩阵存边：n = 5000 时 25×10⁶ 个 int = 100 MB，加上别的开销直接 MLE；遍历一个点还要扫 n 格，m 小的时候反而更慢 → TLE。邻接表是唯一选择。
关掉页面，把 P1113 的 40 行从零敲一遍。用这组数据验证：1 5 0 / 2 3 1 0 / 3 2 1 0 / 4 4 2 3 0 / 5 1 4 0，答案应该是 13。
改一改①：换一组数据 1 5 0 / 2 3 1 0 / 3 9 1 0 / 4 2 2 0，正确答案是 14。把 ans = max(ans, f[u]) 删掉，循环后改成 ans = f[n]，重跑得到 10——f[n] 只是“编号最大的那项杂务”，不是全局最晚。
改一改②：回到第一组数据，把 if (--in[v] == 0) 改成 if (in[v] == 0)。程序不崩，但只有 1 号点出队，ans 变成 5。这就是“忘了自减”的症状。
改一改③：把 queue 换成 stack（front 改 top），出队顺序会变（合并点被提前处理），但 ans 仍然是 13——只要顺序合法，最长路的值与拓扑序的选取无关。
改一改④：把第一行改成 1 5 4 0（让 1 号依赖 4 号），图里就有环了。补上 cnt 判环，确认程序报“有环”，而不是输出一个偏小的数或死循环。
引理一：有向图有拓扑序 ⟺ 无环。
（⇒）若有环 x₁→x₂→…→xₖ→x₁，拓扑序要求 x₁ 在 x₂ 前、x₂ 在 x₃ 前……、xₖ 在 x₁ 前，串起来得到“x₁ 在 x₁ 之前”，矛盾。
（⇐）反设图无环但每个点入度都 ≥ 1。任取一点，沿入边往回走：每一步都有入边，走 n 步必然重复经过某个点，重复的那一段就是环，矛盾。所以无环图必存在入度为 0 的点。删掉它（连同它的出边），剩下的图仍无环，归纳即得拓扑序。这段证明就是 Kahn 算法本身——它每一步都在执行“找出入度为 0 的点”。
引理二：拓扑序一般不唯一。个数可以差得极远：
| 图（n 个点） | 拓扑序个数 | 原因 |
|---|---|---|
| 链 1→2→…→n | 1 | 每对相邻点都被约束定死 |
| 无边（n 个孤立点） | n! | 任意排列都合法；n = 10 时是 3 628 800 |
| 1→3、2→3 | 2 | 1 和 2 谁先都行 |
| 完全 DAG（i→j 对所有 i<j） | 1 | 任意两点都有约束，只剩自然序 |
两个可以直接用的推论：① n ≥ 21 时 n! 已超出 long long（20! ≈ 2.43×10¹⁸，21! ≈ 5.11×10¹⁹），所以“数拓扑序个数”绝不能靠枚举，要用状压 DP（第 34 节），n ≤ 20 时才做得了。② 判断“能否确定唯一顺序”，就是看每一轮入度为 0 的点是否恰好只有一个。
引理三：DAG 上的最长路 = 无限并行下的最短完工时间。这条把抽象的最长路和现实的时间挂上了钩。
取本节的例子：5 项杂务，耗时分别是 5、3、2、4、1，边为 1→2、1→3、2→4、3→4、4→5。f₁ = 5，f₂ = 8，f₃ = 7，f₄ = max(8, 7) + 4 = 12，f₅ = 13。
串行做完的总耗时是 5+3+2+4+1 = 15；如果人多到可以无限并行，总耗时是最长路 13——省下来的 2 正是 3 号杂务与 2 号杂务并行掉的那一段。最长路就是这条依赖链上的“关键路径”，它一秒都省不掉。
反过来也要警惕：一旦限制“同一时刻最多 k 个人干活”，问题立刻从 O(n+m) 变成 NP-hard 的调度问题，赛题不会这么出。看到“k 台机器 / k 个人 / k 条流水线”这类字眼，先想清楚它是不是改变了问题类型。
--in[v] == 0 里“先减再判”的顺序为什么不能反，反了会错成什么样。生态系统中有 n 种生物，它们构成一张食物网：若生物 a 被生物 b 吃，则有一条从 a 指向 b 的边。
一条“最大食物链”指从生产者（入度为 0 的生物）出发，到最高级消费者（出度为 0 的生物）结束的一条有向路径。
求这张食物网中最大食物链的条数，答案对 80112002 取模。
输入格式：第一行两个整数 n、m（1 ≤ n ≤ 5000，1 ≤ m ≤ 500000）。
接下来 m 行，每行两个整数 a、b，表示 a 被 b 吃（即存在边 a→b）。
输出格式：一行一个整数，表示最大食物链的条数 mod 80112002。
链条数 = 从所有入度为 0 的点出发、到所有出度为 0 的点结束的路径总数。起点和终点都可能有很多个。
对每个点记录“有多少条路径能到达它”。一条边 u→v 会把 u 的数目整个加到 v 上——这是加法原理。
拓扑序保证你算到 v 时，所有能到 v 的点都已经算完了；最后把所有出度为 0 的点的数目加起来。
状态。f[u] = 从任意生产者出发、走到 u 的路径条数。
初值。每个入度为 0 的点（生产者）自己算一条“长度为 0 的前缀”，f = 1。注意是所有生产者，不是某一个。
转移。由加法原理，到达 v 的路径 = 所有前驱 u 的路径各自拼上边 u→v。所以对每条边 u→v 做一次 f[v] += f[u]。拓扑序保证算 f[v] 时每个 f[u] 都已经定稿。
答案。最大食物链必须以最高级消费者（出度为 0）结束，所以把所有出度为 0 的点的 f 加起来，边加边取模。
为什么不能直接 DFS 数路径。路径数可能是指数级，DFS 会重复走同一批子路径；记忆化能救，但拓扑 DP 更直接：每个点的 f 只算一次，O(n+m)。
规模。n ≤ 5000、m ≤ 5×10⁵，邻接表存 5×10⁵ 条边约 2 MB；拓扑排序 + 一次 DP，总操作不到 10⁶。
取模。MOD = 80112002，不是常见的 10⁹+7。每次加法后立刻取模，别攒到最后，否则 int 溢出。
边界。只有一个点、没有边时（若数据允许），它是生产者也是消费者，按 out == 0 统计会把它算成一条链；本题数据不出现这种孤立生物，换个题面时要留意。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, MOD = 80112002;
vector<int> g[N]; // 邻接表：m 最大 5×10^5，绝不能开矩阵
int in[N], out[N]; // 入度用于拓扑排序，出度用于找终点
int f[N]; // f[u]：到达 u 的路径条数
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b; // a 被 b 吃
g[a].push_back(b); // 边 a → b
++in[b]; // b 多了一个前驱
++out[a]; // a 有一个后继，不再是最高级消费者
}
queue<int> q;
for (int i = 1; i <= n; ++i)
if (in[i] == 0) { // 所有生产者都是起点
f[i] = 1;
q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
f[v] = (f[v] + f[u]) % MOD; // 加法原理，边加边取模
if (--in[v] == 0) q.push(v);
}
}
int ans = 0;
for (int i = 1; i <= n; ++i)
if (out[i] == 0) // 出度为 0：最高级消费者
ans = (ans + f[i]) % MOD;
cout << ans << "\n";
return 0;
}| 片段 | 作用 |
|---|---|
++in[b]; ++out[a]; | 读一条边同时统计入度和出度。入度给拓扑排序用，出度给最后找终点用，两个都不能少。 |
if (in[i] == 0) { f[i] = 1; q.push(i); } | 所有生产者都是起点，各自算一条“空前缀”。只把某一个点当起点是本题最常见的错。 |
f[v] = (f[v] + f[u]) % MOD; | 到达 v 的路径 = 每个前驱 u 的路径拼上 u→v，直接相加。写成 max 就变成求最长路，全错。 |
if (--in[v] == 0) q.push(v); | 前驱全部处理完才能轮到 v，这样 f[v] 在入队时已经收集完所有前驱的贡献。 |
if (out[i] == 0) ans += f[i] | 终点可能有很多个，必须全部累加。只加“编号最大的那个点”或只加 f[n] 都会漏。 |
const int MOD = 80112002; | 题目指定的模数，不是 1e9+7。抄错模数 = 全篇 WA。 |
vector<int> g[N]; | m ≤ 5×10⁵，邻接表存 2 MB 左右；换成 5000×5000 的 int 矩阵就是 100 MB，直接 MLE。 |