这一节不写代码，只帮你建立全局地图。看完你就知道后面 9 章分别解决什么问题、CSP-J 会怎么考。
图 = 一堆点 + 连接这些点的边。点表示「对象」，边表示「关系」。地铁线路图、微信好友、课程先修关系、地图上的城市公路，本质都是图。
前面你学的数组、链表、栈、队列、树，都是「有严格层次或顺序」的结构；而图最自由——任何两个点之间都可以相连，还可以有方向、有长度。正因为自由，它才能描述真实世界里绝大多数「关系型」问题，也正因此，图论是 CSP-J/S 的必考板块。
站点 = 点，相邻两站 = 边，两站距离 = 边权。求「最少坐几站」就是无权最短路，求「最短里程」就是带权最短路。
课程 = 点，「学 B 之前必须先学 A」= 有向边 A→B。判断能不能安排学习顺序，就是拓扑排序。
村庄 = 点，可修公路 = 带权边。要用最少的总花费让所有村连通，就是最小生成树。
| 章节 | 核心内容 | 难度 | CSP-J 考法 |
|---|---|---|---|
| 第 1 章 | 图的基本概念：有向/无向、度、路径、环、连通、完全图、二分图 | 入门 | 初赛概念题、握手定理计算 |
| 第 2 章 | 三种存储：邻接矩阵、vector 邻接表、链式前向星 | 入门 | 初赛复杂度/结构选择、复赛建图 |
| 第 3 章 | DFS / BFS 遍历、连通块、网格搜索、二分图染色 | 基础 | 复赛 T1/T2 搜索题、连通块计数 |
| 第 4 章 | 拓扑排序（Kahn）、判环、字典序最小、DAG 上 DP | 基础 | 依赖关系、判环、DAG 最长路 |
| 第 5 章 | Floyd 多源最短路、三重循环顺序陷阱 | 基础 | n ≤ 500 的任意两点最短路 |
| 第 6 章 | Dijkstra 朴素 + 堆优化、为什么怕负边 | 重点 | 单源最短路主力算法 |
| 第 7 章 | Bellman-Ford、SPFA、负环判定、分层图 | 重点 | 负权边、判负环、状态分层 |
| 第 8 章 | 最小生成树：Kruskal（并查集）、Prim | 重点 | 修路/连通代价最小 |
| 第 9 章 | 进阶选学：Tarjan 强连通分量、割点与桥、次小生成树、二分图匹配 | 提高 | CSP-S / NOIP 衔接 |
INF、dis[i][i]=0；链式前向星要 memset(head,-1,sizeof head)。漏一步就是全 WA。add(u,v) 之后必须 add(v,u)。这个错误极其常见。vis，而不是出队时，否则同一个点会重复入队、内存爆炸。k 必须是最外层循环，否则 DP 的阶段顺序错了，结果错误（第 5 章会详细解释为什么）。这一章全是「名词解释」，但初赛选择题几乎年年考。概念不清，后面所有算法都会学得含糊。
一个图用二元组 G = (V, E) 表示：
例如右图：V = {1,2,3,4}，E = {(1,2),(2,3),(1,3),(3,4)}，记作 n = 4 个点、m = 4 条边。
(u, v)，是无序二元组(u,v) 和 (v,u) 是同一条边u → v，是有序二元组u→v 与 v→u 是两条不同的边无向图中，顶点 v 的度 deg(v) = 与 v 相连的边的条数。自环会让度 +2（因为它的两个端点都是 v）。
有向图中，度要分两种：
deg(v) = indeg(v) + outdeg(v)| 名词 | 定义 | 直白理解 |
|---|---|---|
| 路径 | 边的序列 e₁,e₂,…,eₖ，且相邻两条边首尾相接，可简写为 v₀→v₁→…→vₖ | 从起点一步步走到终点的一条「走法」 |
| 简单路径 | 路径上的点两两不同（不重复经过同一个点） | 不走回头路 |
| 回路 | 起点 = 终点的路径（v₀ = vₖ） | 绕了一圈回到原点 |
| 环 | 除起点=终点外，其余点都只出现一次的回路 | 最简单的「圈」，中间不重复 |
a→b→c→b→a 是回路，但中间 b 出现了两次，不是环。a→b→a 算回路，但通常不把它当作有意义的环（长度 2 的环在有向图中要求两条方向相反的边）。若 u 到 v 存在路径，称 u 与 v 连通。若图中任意两点都连通，称该图是连通图；否则叫非连通图。
非连通图可以拆成若干个「极大的连通子图」，每个叫一个连通分量（连通块）。「极大」的意思是：再加任何一个点进来就不再连通了。
有向图中若存在 u→…→v 的路径，称 u 可达 v（记 u ⇝ v）。注意可达是单向的：u 能到 v，不代表 v 能到 u。
若图中任意两个点互相可达，称该图强连通。有向图的「极大强连通子图」叫强连通分量（SCC），第 9 章会讲 Tarjan 求它。
只要「能走过去」即可，方向无所谓。求连通块个数用 DFS/BFS 扫一遍（第 3 章）。
要求「来回都能走」。例如 a↔b↔c 构成环，这 3 个点就在同一个 SCC 里。
任意两点之间都有边。n 个点的无向完全图边数：
m = n(n−1)/2
有向完全图（任意两点双向都有边）：m = n(n−1)。
边数远小于 n² 的叫稀疏图（如 m ≈ n）；边数接近 n² 的叫稠密图。
没有严格界限，作用是帮你选算法：稀疏图用 O(m log m) 的堆优化 Dijkstra / Kruskal；稠密图可用 O(n²) 的朴素 Dijkstra / Prim。
无自环、无重边的图。自环是 u=u 的边；重边是两个端点都相同的多条边。
无向图中 (u,v) 与 (v,u) 算重边；有向图中 u→v 与 v→u 不算重边。
能把点集分成 X、Y 两部分，使每条边的两个端点分别落在不同部分。
等价判定：图中不存在奇环（长度为奇数的环）。可用 DFS/BFS 黑白染色判定（第 3 章）。
思路：设总点数为 n。所有点的度数之和 = 2m = 24。
握手定理：Σdeg = 2m = 2×12 = 24。
设总点数 n，则其余点有 (n−5) 个，度数和为：5×4 + (n−5)×2 = 2n + 10。
解 2n + 10 = 24，得 n = 7。
答案：7 个点。
检验：5×4 + 2×2 = 24 = 2×12 ✓
「最多」对应完全图；「最少」还要保证连通。
最多：任意两点都有边，共 C(n,2) = n(n−1)/2 条。
最少：连通只需 n−1 条边（构成一棵树）。少一条就不连通了。
答案：最多 n(n−1)/2，最少 n−1。
由此可得一个常用结论：n 个点的连通图，边数 m 满足 n−1 ≤ m ≤ n(n−1)/2。
A. 8 B. 9 C. 10 D. 11
思路：要让点数最少，就要把边「塞得最密」——先让一个连通分量尽量接近完全图，再加至少 1 个孤立点保证「非连通」。
设主连通分量有 k 个点，则最多 k(k−1)/2 条边，要求 k(k−1)/2 ≥ 36。
k = 9 时：9×8/2 = 36，刚好；k = 8 时只有 28 条，不够。
但只有 9 个点时，36 条边意味着它是完全图 K₉，此时图是连通的，不满足「非连通」。
所以必须再加 1 个孤立点：9 + 1 = 10。
答案：C（10 个点）。
A. 每个顶点的度数至少为 1 B. 任意两个顶点之间都有边相连
C. 任意两个顶点之间都有路径相连 D. 每个顶点至少都连有一条边
强连通 ⇒ 任意两点互相可达 ⇒ 不存在孤立点，因此 A、D 正确；C 正是强连通的定义。
但强连通不要求两点之间直接有边。反例：4 个点顺时针连成一个环 1→2→3→4→1，它是强连通的，却没有对角线（1 和 3 之间没有边）。
答案：B。
记住这个反例：环是强连通但不是完全图。
本章概念看起来「只能背」，但初赛的计算题、复赛的建图题都建立在这些定义上。下面 3 道题把「度」「简单图」「完全图」变成可以直接运行的代码——写一遍比背十遍牢。
读入 n 个点、m 条无向边（点编号 1..n，可能存在重边与自环）。要求输出：① 每个点的度数；② 所有点的度数之和；③ 若度数之和等于 2m 输出 YES，否则 NO。
第一行 n m；接下来 m 行每行两个整数 u v，表示一条无向边。
第一行 n 个整数；第二行一个整数；第三行 YES 或 NO。
输入：
4 4
1 2
2 3
1 3
3 3
输出：
2 2 4 0
8
YES为什么 3 号点是 4 度：它连着 1、2 各一次（2 度），还有一个自环 3-3。自环给该点贡献 2 度，因为从 3 出发沿这条边走到 3，出和入各算一次。
思路：一遍扫描累加度数，自环特殊处理加 2。因为每条边贡献 2 度，所以总和必然是偶数，直接和 2m 比较即可验证握手定理。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int deg[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
if (u == v) deg[u] += 2; // 自环：对同一个点贡献 2 度
else { deg[u]++; deg[v]++; } // 普通边：两端各 +1
}
long long sum = 0;
for (int i = 1; i <= n; i++) { printf("%d ", deg[i]); sum += deg[i]; }
printf("\n%lld\n", sum);
puts(sum == 2LL * m ? "YES" : "NO");
return 0;
}int deg[100005] 约 400KB，放 main 里会占栈空间（Windows 默认栈只有 1~2MB），n 再大一点就 爆栈。全局变量在静态区，空间大得多，且默认全 0，不用手动清零。scanf("%d%d", &n, &m) 对应题面的 n m，其中 m 是边数，控制后面的循环次数。这是最容易被自己写反的一处。deg[u]++ 和 deg[v]++ 都要写。只写一行是最常见的 bug，表现为「所有度数都偏小、总和 = m 而不是 2m」。puts(条件 ? "YES" : "NO") 是三目运算符的常见写法，比 if-else 短一半。注意 2LL * m 里的 LL——它把 m 提升为 long long 再相乘，防止大数溢出。outdeg[u]++; indeg[v]++;，且不再有自环加 2 的问题（自环给出度、入度各 +1）。第 4 章拓扑排序的入度就是这么算的。简单图指：没有自环（两端相同的边），也没有重边（同一对点之间出现多次）。给定一个无向图，判断它是否是简单图。若不是，输出第一个发现的违规原因（自环 或 重边）。
输入：
3 4
1 2
2 3
1 2
3 1
输出：
NO 重边
说明：1-2 出现了两次（注意 1 2 与 2 1 是同一条边）思路：n ≤ 1000，可以用 bool g[1005][1005] 记住每条边是否出现过。读一条边就检查：两端相同 → 自环；已经标记过 → 重边。边读边判，发现即退出。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
bool g[N][N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
if (u == v) { puts("NO 自环"); return 0; }
if (g[u][v]) { puts("NO 重边"); return 0; }
g[u][v] = g[v][u] = true; // 无向图：两个方向都标记
}
puts("YES");
return 0;
}bool，只占 1MB。如果 n 是 10⁵，就该换 set<pair<int,int>> 或哈希表了。数据结构的选择永远由数据范围决定。g 数组，时间复杂度 O(m)。u == v，如果先查 g[u][v] 也成立（因为上一轮可能已标记），会把「自环」误报成「重边」。判断顺序要按「更特殊的先查」。g[u][v] 为真说明这条边来过。注意输入给的是 1 2 还是 2 1 都算同一条边，所以下一步必须两个方向都置真。g[u][v] = g[v][u] = true; 是链式赋值的写法，等价于两条独立语句。无向图的矩阵永远关于主对角线对称，这是检查自己代码有没有写漏的好办法。g[u][v] = true 而不写 g[v][u]，那么输入 1 2 后再输入 2 1 会被判成「不是重边」——因为查的是 g[2][1]，还是 false。n 个点的完全图指任意两点之间都有一条边，边数为 n(n−1)/2。给定 n 和 m 条已有的边（保证是简单图），求：① 完全图的边数；② 补图的边数（补图 = 完全图去掉这些边后剩下的边）。
输入：
4 3
输出：
6
3思路：公式直接算。all = n*(n-1)/2，comp = all - m。唯一的难点在溢出：n = 2×10⁹ 时 n(n−1) ≈ 4×10¹⁸，已经接近 long long 的上限 9.2×10¹⁸，用 int 会直接变负数。
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n; long long m;
scanf("%lld%lld", &n, &m);
long long all = n * (n - 1) / 2; // 先乘后除
long long comp = all - m;
printf("%lld\n%lld\n", all, comp);
return 0;
}all - m 这类运算，混用 int 就可能在中途被截断。题目给了 2×10⁹ 这种范围，就一个 int 都别留。n * (n-1) / 2 而不是 n/2 * (n-1)：C++ 的整数除法会向下取整。n 是奇数时 n/2 会丢掉 0.5，结果偏小；而 n 与 n−1 中必有一个偶数，所以先乘后除一定整除，结果精确。__int128 或高精度了。%lld 与 long long 必须配对：用 %d 打印 long long 是未定义行为，通常表现为输出一个莫名其妙的数。这是新手调试时最抓狂的 bug 之一。算法写得对不对，一半取决于图存得对不对。三种方式各有适用场景，竞赛里最常用的是「vector 邻接表」和「链式前向星」。
无论用哪种结构，目标都是支持两个操作：
第 2 个操作是所有图算法的核心——DFS、BFS、Dijkstra、拓扑排序、Prim，全都在反复做「枚举 u 的邻居」。
开一个 n×n 的二维数组 a[i][j]，表示 i 到 j 有没有边（或边权是多少）：
| 类型 | a[i][j] 的含义 |
|---|---|
| 无权图 | a[i][j] = 1 表示有边，0 表示无边 |
| 带权图 | a[i][j] = w 表示边权；无边记 INF；a[i][i] = 0 |
const int N = 1010;
const int INF = 0x3f3f3f3f;
int a[N][N]; // a[i][j] = 边权，无边为 INF，自己到自己为 0
int main() {
int n, m;
cin >> n >> m;
// 1) 初始化：先全部置为“不可达”
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = (i == j ? 0 : INF);
// 2) 读入 m 条边
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
a[u][v] = min(a[u][v], w); // 有重边时保留最小的
a[v][u] = min(a[v][u], w); // 无向图：反向也要存！
}
// 3) 枚举 u 的所有邻居
int u = 1;
for (int v = 1; v <= n; v++)
if (a[u][v] != INF && u != v)
cout << "邻居 " << v << " 边权 " << a[u][v] << endl;
return 0;
}a[u][v] 直接访问int 约 100MB，已经很危险；n ≤ 2000 才比较安全。所以邻接矩阵只适合 n 小的题（比如 Floyd 题 n ≤ 500）。给每个点开一个 vector，里面装它所有的出边。用 pair<int,int> 同时存「终点」和「边权」。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<pair<int,int>> g[N]; // g[u] = {(终点 v, 边权 w), ...}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w}); // 有向边 u→v
g[v].push_back({u, w}); // 如果是无向图，加这一行
}
// 遍历 u 的所有邻居
int u = 1;
for (auto &e : g[u]) {
int v = e.first, w = e.second;
cout << u << " -> " << v << " , w = " << w << endl;
}
return 0;
}vector<int> g[N];
// 建边
g[u].push_back(v);
g[v].push_back(u); // 无向图
// 遍历
for (int v : g[u]) cout << v << " ";vector 的 push_back 会动态扩容。数据量大时建议先 g[u].reserve(deg[u])，或者直接用链式前向星。思路：把所有边存在一个数组里，再用一个 head 数组记录「每个点的第一条边在哪」。每条边再记一个 nxt，指向「同起点的下一条边」，形成一条链表。
| 数组 | 含义 |
|---|---|
head[u] | 以 u 为起点的第一条边在 Edge 数组中的下标（没有则为 −1） |
Edge[i].to | 第 i 条边的终点 |
Edge[i].w | 第 i 条边的权值 |
Edge[i].nxt | 第 i 条边同起点的下一条边的下标（没有则为 −1） |
const int N = 1e5 + 5; // 点数
const int M = 2e5 + 5; // 边数（无向图要开 2 倍！）
struct Edge {
int to, nxt, w;
} e[M];
int head[N], cnt = 0;
void add(int u, int v, int w) {
e[++cnt].to = v; // 这条边指向 v
e[cnt].w = w; // 边权
e[cnt].nxt = head[u]; // 接在 u 原来的第一条边前面
head[u] = cnt; // u 的第一条边变成新加的这条
}
int main() {
memset(head, -1, sizeof(head)); // -1 表示“没有边”
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
add(u, v, w);
add(v, u, w); // 无向图才需要
}
// 遍历 u 的所有出边
for (int i = head[u]; i != -1; i = e[i].nxt) {
int v = e[i].to, w = e[i].w;
}
}to[M]、nxt[M]、w[M]。结构体的好处是「一条边的信息连着放」，缓存友好；缺点是不同写法（结构体 / 三数组）不能混用，抄模板时要整套抄。head[u] 存的是「u 的链表头那条边的编号」，不是邻居编号，也不是边数。cnt 从 0 开始，每 add 一次先自增再使用，所以边编号是 1..m，0 号位置永远空着——这样才能用 −1 当「没有边」的哨兵。to 和 w。这两句顺序无所谓，但必须在改 head 之前完成。e[cnt].nxt = head[u]（新结点接上旧链表），再 head[u] = cnt（头指针前移）。如果先改 head，旧链表头就丢了，整条链断掉——这是最经典的指针操作失误。memset(head, -1, sizeof(head)) 必须写，且必须在任何 add 之前。漏了 head 全是 0，遍历时会把 0 号边当成真实边读，输出垃圾数据。add(v, u, w) 是无向图的标志。有向图删掉这一行即可；但如果删了却按无向图理解题意，答案会系统性偏大（很多点变得不可达）。i = head[u]、终止 i != -1、步进 i = e[i].nxt。漏掉任何一项都会死循环或漏边。注意这里是 i 是边编号，取终点要写 e[i].to 而不是 to[i]（除非你用的是三数组写法）。add 都把新边插在链表头部（e[cnt].nxt = head[u]; head[u] = cnt;），所以遍历时边的顺序和输入顺序相反。大多数题不在意顺序；若要求「按输入顺序」输出，用 vector 或把边倒着存。依次加入：① 1→2（权 5） ② 1→3（权 7） ③ 2→3（权 4） ④ 1→4（权 2）
head[1..4] = -1，cnt = 0。此时没有任何边。++cnt = 1；e[1] = {to=2, nxt=head[1]=−1, w=5}；head[1] = 1。++cnt = 2；e[2] = {to=3, nxt=head[1]=1, w=7}；head[1] = 2。++cnt = 3；e[3] = {to=3, nxt=head[2]=−1, w=4}；head[2] = 3。++cnt = 4；e[4] = {to=4, nxt=head[1]=2, w=2}；head[1] = 4。i = head[1] = 4 → 输出 4；i = e[4].nxt = 2 → 输出 3；i = e[2].nxt = 1 → 输出 2；i = e[1].nxt = −1 结束。for (int i = head[u]; ~i; i = e[i].nxt) 里的 ~i 等价于 i != -1（−1 的二进制全是 1，取反为 0，循环结束）。很多模板这么写，看到别慌。初学建议写 i != -1 更清楚。| 对比项 | 邻接矩阵 | vector 邻接表 | 链式前向星 |
|---|---|---|---|
| 空间 | O(n²) | O(n + m) | O(n + m) |
| 查边 u→v | O(1) | O(deg(u)) | O(deg(u)) |
| 枚举邻居 | O(n) | O(deg(u)) | O(deg(u)) |
| 建图 | O(n² + m) | O(n + m) | O(n + m) |
| 适合 | 稠密图、n 小、Floyd | 通用、好写 | 大数据、卡常数 |
| 无向图注意 | 对称赋值 | 两次 push_back | M 开 2 倍 |
存图方式光看书没用，必须亲手写三遍：矩阵读进来转邻接表、前向星建完再遍历、邻接表去重排序。这三个动作覆盖了复赛 90% 的建图代码。
读入一个有向图的邻接矩阵（a[i][j] = 1 表示有一条 i→j 的边），把它转换成邻接表输出。要求每个点的邻居按编号升序排列。
输入：
4
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
输出：
1: 2 3
2: 1 4
3: 1
4: 2思路：双重循环扫矩阵，遇到 1 就把列号 j 推进 e[i]。因为内层 j 是从小到大扫的，push 的顺序天然升序，不需要额外排序。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; scanf("%d", &n);
vector<vector<int>> e(n + 1); // 下标 1..n
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
int x; scanf("%d", &x);
if (x) e[i].push_back(j);
}
for (int i = 1; i <= n; i++) {
printf("%d:", i);
for (int j = 0; j < (int)e[i].size(); j++) printf(" %d", e[i][j]);
printf("\n");
}
return 0;
}vector<vector<int>> e(n+1) 开了 n+1 个空 vector，下标 0 浪费掉不用，这样点编号 1..n 能直接当前标。「多开一个」是所有竞赛代码的通用习惯——后面 e[n] 才是最后一个点，不会越界。if (x) 而不是 if (x == 1)：非 0 即为真。题目若用边权矩阵（0 表示无边、正数表示权值），这个写法同样适用，只是要把 e 换成存 pair<int,int>。(int)e[i].size() 的强制转换：size() 返回的是无符号类型 size_t，与 int j 比较时会触发有符号/无符号警告，某些编译器会报错。养成加 (int) 的习惯。"%d:"，再循环打印 " %d"（前面带空格），最后补一个换行。这样不会出现行末多余空格，也不会漏掉冒号——是刷题时最省心的写法。a[i][j] 和 a[j][i] 都是 1，两边都会各自 push，正好得到双向邻接表。用链式前向星存一个有向带权图（m 条边，每条 u v w），然后按链式遍历的顺序输出每个点的所有出边，格式 u: (v1,w1) (v2,w2) ...。
输入：
4 5
1 2 5
1 3 7
2 4 2
3 4 9
1 4 1
输出：
1: (4,1) (3,7) (2,5)
2: (4,2)
3: (4,9)
4:注意输出是逆序的：1 号点先加了 2、再 3、再 4，但头插法让最后加的排在最前面。这不是 bug，而是链式前向星的固有特性——遍历顺序与加边顺序相反。很多题（比如求最小字典序路径）需要正序，那时就要额外排序或改用邻接表。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, M = 200005;
int head[N], nxt[M], to[M], wt[M], tot;
void add(int u, int v, int w) {
to[++tot] = v; wt[tot] = w;
nxt[tot] = head[u]; head[u] = tot;
}
int main() {
memset(head, -1, sizeof head); // 必须！-1 表示链表结束
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
add(u, v, w); // 有向图：只加一条
}
for (int u = 1; u <= n; u++) {
printf("%d:", u);
for (int i = head[u]; i != -1; i = nxt[i])
printf(" (%d,%d)", to[i], wt[i]);
printf("\n");
}
return 0;
}head[u] 存「u 的最后一条出边的编号」；to[i] 存第 i 条边的终点；wt[i] 存权值；nxt[i] 存「同起点的上一条边编号」；tot 是边的计数器。把一条边想象成链表结点，head 就是链表头。to 和 wt（写数据）；②nxt[tot] = head[u]（新结点指向原链表头）；③head[u] = tot（更新头指针）。如果先改 head 再取 nxt，就会丢掉整条旧链表。memset(head, -1, sizeof head) 是整个模板里最容易漏的一行。漏了会怎样？head 全是 0，遍历时 i = 0 不是 −1，于是把编号 0 当成一条边去读 to[0]，输出一堆垃圾甚至死循环。i != -1，不是 i > 0：因为边编号从 1 开始，0 号边不存在，用 −1 作哨兵才能正确终止。写成 i > 0 恰好也对，但若以后改成 0-index 就会出错，统一用 != -1 更稳。head 想成「一串挂钩」，每次 add 都是把新牌子挂在最外面。所以遍历时看到的是「最后挂上去的」最先出现——这就是逆序的由来。读入一个无向图，其中可能有重边和自环。请对每个点去重（自己到自己的自环也去掉），并把邻居按编号升序输出。
输入：
4 7
1 2
2 1
1 3
1 2
3 4
2 3
4 4
输出：
1: 2 3
2: 1 3
3: 1 2 4
4: 3思路：仍然用 vector 邻接表，建完图后对每个点执行 sort + unique（先去重再排序，或者先排序再去重——后者才是标准写法，因为 unique 只能消除相邻的重复元素）。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m; scanf("%d%d", &n, &m);
vector<vector<int>> e(n + 1);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
if (u == v) continue; // 自环直接丢掉
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
sort(e[i].begin(), e[i].end()); // 先排序
e[i].erase(unique(e[i].begin(), e[i].end()), e[i].end()); // 再去重
printf("%d:", i);
for (int j = 0; j < (int)e[i].size(); j++) printf(" %d", e[i][j]);
printf("\n");
}
return 0;
}if (u == v) continue;。如果放到后面去重，也能去掉（因为只 push 了一次），但要多跑一轮 unique。能在源头拦掉就别留到后面处理。e[u] 加 v、e[v] 加 u。这也是为什么重边会「双倍出现」——一次 1 2 会在 1 的表里塞一个 2，一次 2 1 又塞一个。sort 再 unique。unique 的作用是「把相邻的重复元素移到末尾」，它不排序。对 2 1 3 2 用 unique 什么都不会删，因为两个 2 不相邻。erase(unique(...), end()) 是固定搭配：unique 返回「去重后新区间的尾后迭代器」，erase 把从这里到 end() 的垃圾元素真正删掉。两句要连在一起写，缺一不可。遍历是图论的「万能钥匙」：连通块、判环、最短路、拓扑排序、强连通分量，全都建立在遍历之上。
思想：从起点出发，沿着一条路一直往前走，走不动了就回退到上一个还能走别的路的点，继续深入。这正好对应递归。
int vis[N];
void dfs(int u) {
vis[u] = 1; // 一进来就标记，防止绕圈
cout << u << " "; // 访问 u（按题目要求做事）
for (int v : g[u]) {
if (!vis[v]) dfs(v); // 没访问过才继续深入
}
}
int main() {
// ...
for (int i = 1; i <= n; i++)
if (!vis[i]) dfs(i); // 非连通图：每个未访问点都起一次 DFS
}思想：从起点出发，先把「距离为 1」的全部访问完，再访问「距离为 2」的，像水波一样一层层扩散。用队列实现。
int vis[N], dist[N];
queue<int> q;
void bfs(int s) {
vis[s] = 1;
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (vis[v]) continue;
vis[v] = 1; // 关键：入队时就标记！
dist[v] = dist[u] + 1; // 无权图：边数就是距离
q.push(v);
}
}
}vis[v] = 1 写在「出队时」而不是「入队时」：同一个点可能被多个邻居重复入队，队列膨胀到 O(m)，甚至死循环。入队即标记，一遍就够。题目（Oil Deposits）：一块 n×m 的矩形区域，@ 表示有油，* 表示没有。若两个 @ 在水平、垂直或对角方向相邻（8 个方向），它们属于同一油藏。问一共有多少块油藏。n, m ≤ 100。
@ 格子当成一个点，相邻（8 方向）的两个 @ 之间连边。问题就变成：求无向图的连通块个数。int n, m;
char c[105][105];
int dx[8] = {-1,-1,-1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1,-1, 1,-1, 0, 1};
void dfs(int x, int y) {
c[x][y] = '*'; // 标记为已访问（直接改成石头，省一个 vis 数组）
for (int k = 0; k < 8; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && c[nx][ny] == '@')
dfs(nx, ny);
}
}
int main() {
while (cin >> n >> m && n) { // 多组数据，n=0 结束
for (int i = 0; i < n; i++) cin >> c[i];
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (c[i][j] == '@') { // 发现一个新的连通块
ans++;
dfs(i, j); // 把整块都标记掉
}
cout << ans << "\n";
}
return 0;
}dx/dy 为 4 个，八方向用 8 个，这是唯一区别。
题目（洛谷 P3916 图的遍历）：给出 n 个点、m 条边的有向图，对每个点 v，求从 v 出发能到达的编号最大的点 A(v)。1 ≤ n, m ≤ 10⁵。
对每个点各做一次 DFS，求能到达的最大编号。复杂度 O(n(n+m))，n = 10⁵ 时约 10¹⁰，直接 TLE。
「v 能到 u」等价于「在反图中 u 能到 v」。那么从编号大的点出发，在反图上能走到的所有点，答案都是这个大编号。
u→v，实际存 v→u；vector<int> g[N];
int ans[N];
void dfs(int u, int root) {
if (ans[u]) return; // 已经被更大的编号“认领”过了
ans[u] = root; // 当前起点 root 能到 u，答案就是 root
for (int v : g[u]) dfs(v, root);
}
int main() {
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
g[v].push_back(u); // 反向建图：原图 u→v，反图 v→u
}
for (int i = n; i >= 1; i--) // 从大到小
if (!ans[i]) dfs(i, i);
for (int i = 1; i <= n; i++) cout << ans[i] << " ";
return 0;
}题：n×m 的迷宫，. 可走、# 墙壁，从起点 S 走到终点 T，每步上下左右移动一格，求最少步数。
把每个可走格子当点，相邻格子连边（边权都是 1）。边权相同的图，BFS 第一次到达就是最短。
struct Node { int x, y; };
int n, m, dist[1005][1005];
char mp[1005][1005];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int bfs(int sx, int sy, int tx, int ty) {
memset(dist, -1, sizeof(dist)); // -1 表示未访问
queue<Node> q;
q.push({sx, sy});
dist[sx][sy] = 0;
while (!q.empty()) {
Node u = q.front(); q.pop();
if (u.x == tx && u.y == ty) return dist[u.x][u.y];
for (int k = 0; k < 4; k++) {
int nx = u.x + dx[k], ny = u.y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (mp[nx][ny] == '#' || dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[u.x][u.y] + 1;
q.push({nx, ny});
}
}
return -1; // 走不到
}判定标准：一个图是二分图 ⇔ 可以用两种颜色给点染色，使每条边的两端颜色都不同 ⇔ 图中没有奇环。
做法：从每个未染色的点出发 BFS（或 DFS），把它染成 1，邻居染成 2，邻居的邻居染成 1……如果发现某条边的两端颜色相同，立即判定「不是二分图」。
vector<int> g[N];
int col[N]; // 0=未染色, 1=颜色A, 2=颜色B
bool check(int n) {
for (int s = 1; s <= n; s++) {
if (col[s]) continue; // 每个连通块都要检查
queue<int> q;
q.push(s);
col[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (!col[v]) {
col[v] = 3 - col[u]; // 1 变 2，2 变 1
q.push(v);
} else if (col[v] == col[u]) {
return false; // 相邻同色 → 不是二分图
}
}
}
}
return true;
}| 对比项 | DFS（深度优先） | BFS（广度优先） |
|---|---|---|
| 实现 | 递归 / 栈 | 队列 |
| 访问顺序 | 一条路走到底，再回退 | 按距离一层层扩散 |
| 空间 | O(递归深度)，最坏 O(n) | O(队列宽度)，最坏 O(n) |
| 能否求最短路 | 不能（除非枚举所有路径） | 能（仅限无权/等权图） |
| 擅长 | 连通块、判环、拓扑、回溯搜索、Tarjan | 最短路、分层、多源扩散、二分图染色 |
| 风险 | 深图爆栈 | 宽图队列占内存 |
遍历是图论里唯一「必须靠手感」的部分。下面 3 道题从「数连通块」到「网格搜索」再到「BFS 最短路」，把 DFS 与 BFS 的两套模板各自用一遍。
给定 n 个点、m 条无向边（可能不连通）。求：① 连通块个数；② 每个连通块包含几个点，按升序输出。
输入：
6 4
1 2
2 3
4 5
5 6
输出：
2
3 3思路：外层循环扫每个点，遇到未访问的就说明发现了一个新块 → BFS 把整块染色，同时统计点数。外层循环的次数就是块数。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> e[N];
bool vis[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u); // 无向图：双向加
}
vector<int> sz;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue; // 已属于某个块，跳过
int cnt = 0; // 本块的点数
queue<int> q;
q.push(i); vis[i] = true; // 入队时就标记！
while (!q.empty()) {
int u = q.front(); q.pop();
cnt++;
for (int j = 0; j < (int)e[u].size(); j++) {
int v = e[u][j];
if (!vis[v]) { vis[v] = true; q.push(v); }
}
}
sz.push_back(cnt);
}
sort(sz.begin(), sz.end());
printf("%d\n", (int)sz.size());
for (int i = 0; i < (int)sz.size(); i++) printf("%d ", sz[i]);
return 0;
}vector<int> e[N] 是全局的「数组套 vector」，等价于二维动态数组。它比 int e[N][N] 省得多：有边的位置才占空间，总容量 2m 而不是 n²。if (vis[i]) continue; 是块计数的核心：只有「从没被任何 BFS 碰过」的点才代表一个新块。这一句同时起到了「计数」和「避免重复遍历」两个作用。vis[i] = true 必须在入队时写，不能挪到出队时。否则同一个点会被它的多个邻居重复入队，队列膨胀到 O(m)，最坏直接把内存吃光（第 3 章讲过的经典坑）。cnt++ 放在出队处：每个点入队一次、出队一次，所以在出队时统计不会重复也不会漏。这是「统计块内点数」最标准的写法。sort 一下最省事。void dfs(int u){ cnt++; vis[u]=true; for(int v:e[u]) if(!vis[v]) dfs(v); } 即可。但要小心：n = 10⁵ 的链状图递归深度也是 10⁵，会爆栈。数据大时优先 BFS。n×m 的网格，# 表示陆地、. 表示水。上下左右相邻的陆地属于同一片区域。求最大区域的格子数。
输入：
5 5
.....
.##..
.###.
..#..
.....
输出：
6思路：网格题不要真的建图——把格子坐标当成点，四个方向就是四条边，「相邻」关系在遍历时现场算出来即可。这就是所谓「隐式图」。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, ans;
char g[N][N];
bool vis[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (g[i][j] != '#' || vis[i][j]) continue;
int cnt = 0;
queue<pair<int,int>> q;
q.push({i, j}); vis[i][j] = true;
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop(); cnt++;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 越界
if (g[nx][ny] != '#' || vis[nx][ny]) continue; // 非陆地/已访问
vis[nx][ny] = true;
q.push({nx, ny});
}
}
ans = max(ans, cnt);
}
printf("%d\n", ans);
return 0;
}dx[k] 与 dy[k] 一一配对：(+1,0) 下、( −1,0) 上、(0,+1) 右、(0,−1) 左。如果题目允许走斜线，再加 4 组 (±1,±1) 变 8 个方向。scanf("%s", g[i] + 1) 是读字符网格的技巧：g[i]+1 是第 i 行第 1 列的地址（跳过下标 0），这样字符就存在 g[i][1]..g[i][m]，与 1-based 的循环一致。%s 会自动在末尾补 \0，不会串行。g[i][j] != '#' || vis[i][j]：非陆地跳过、已访问也跳过。两个条件用 || 合并，任一成立就 continue，比嵌套 if 清爽。queue<pair<int,int>> 存坐标。C++11 起可以用花括号 q.push({i, j}) 直接构造 pair，不必写 make_pair。g[nx][ny] 之前。C++ 不检查数组越界，先读再判会让程序读到别的内存（可能崩溃、也可能算出诡异答案）。「先判边界，再判内容」是网格题的铁律。continue 挡掉两个条件：非陆地或已访问。注意「已访问」这一条不能省，否则两块连在一起时会互相"踢皮球"，在两人之间反复入队直到内存耗尽。max 滚起来，不需要把每块面积都存进数组再排序。题目只要最大值，能省的内存就省。给定有向图（边权全为 1），求起点 s 到每个点的最少经过几条边。不可达输出 -1。
输入：
6 5 1
1 2
1 3
2 4
3 4
4 5
输出：
0 1 1 2 3 -1思路：BFS 按「层」扩展，第 1 层是距离 1 的点，第 2 层是距离 2 的点……所以点第一次被访问时的层数就是最短距离。用一个 dis 数组记录层数即可，不需要任何松弛操作。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> e[N];
int dis[N]; // -1 表示未访问
int main() {
int n, m, s; scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v); // 有向图：只加一条
}
memset(dis, -1, sizeof dis); // 用 -1 同时表示「未访问」
dis[s] = 0;
queue<int> q; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i];
if (dis[v] != -1) continue; // 访问过就不再更新
dis[v] = dis[u] + 1; // 层数 = 上一层 +1
q.push(v);
}
}
for (int i = 1; i <= n; i++) printf("%d ", dis[i]);
return 0;
}dis = -1 代替 vis 数组：一个数组同时表达「有没有访问过」和「距离多少」。判断条件是 dis[v] != -1，赋值就是 dis[u] + 1。能合并的状态就合并，代码更短也更快。dis[s] 还是 −1，会算出 dis[邻居] = 0，全盘错位。if(vis[u])，在 SPFA 里则没有——三者别混。dis[v] = dis[u] + 1：dijkstra 里是加边权 w，BFS 里边权恒为 1，所以加 1。如果把 BFS 写成 dis[v] = dis[u] + w 并允许 w ≠ 1，那就是错的——队列不按距离排序，必须先弹完近的才能保证正确。dis 仍是 −1，直接打印就符合题目要求。如果题目要求输出很大的数（比如 2³¹−1），就把初值改成那个数，但判断条件要跟着改。「先学 A 才能学 B」「先编译模块 A 才能编译 B」——只要题目里出现「先后顺序」，大概率就是拓扑排序。
DAG（Directed Acyclic Graph，有向无环图）：没有回路的有向图。
如果把「任务」当点，「任务 u 必须在 v 之前完成」当有向边 u→v，得到的图叫 AOV 网（Activity On Vertex）。它必须是 DAG，否则说明任务互相依赖、无法开始。
拓扑排序：把 DAG 的所有点排成一个线性序列，使得对每条边 u→v，u 都排在 v 前面。简单说：不破坏先后关系地把图「拉直」。
注意：拓扑序通常不唯一。比如「1→3、2→3」，那么 1 2 3 和 2 1 3 都是合法的拓扑序。
indeg[v]；indeg[v]--，若变成 0 则入队；const int N = 1e5 + 5;
vector<int> g[N];
int indeg[N]; // 入度
vector<int> topo; // 拓扑序
bool kahn(int n) {
queue<int> q;
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 (int v : g[u]) {
if (--indeg[v] == 0) // 一个前置完成后入度减 1
q.push(v); // 所有前置都完成 → 解锁
}
}
return (int)topo.size() == n; // false 说明有环
}
int main() {
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
indeg[v]++; // 建边时统计入度
}
if (!kahn(n)) cout << "Error!" << endl;
else for (int x : topo) cout << x << " ";
return 0;
}g 存邻接表（有向边 u→v）、indeg 存入度、topo 存结果。topo 声明成全局是为了让 kahn 函数能往里写、主函数能读出来。for 扫一遍全图，而不是只放 1 号点——图可能分成多个互不连通的部分，只放一个会漏。--indeg[v] == 0 是「删边」的具体动作：u 完成后，u→v 这条依赖被解除，v 的入度减 1。减到 0 说明 v 的所有前置都完成了，可以入队。先减再判，顺序不能反。topo.size() == n 判环，不要用「队列空了」或「有没有入度 0 的点」。只有「排出来的点数等于总点数」才等价于「无环」。返回 false 时说明有环，环上的点永远出不来。indeg[v]++ 必须在建边时同步完成。若忘了这一句，所有点入度都是 0，一开场全部入队，输出的「拓扑序」只是 1..n 的编号顺序，完全不满足依赖。topo 里只有一部分点，直接打印会得到一串「看起来正常」但不完整的序列，非常容易被忽略。如果图中存在环，环上的点互相等待，入度永远减不到 0，永远不会入队。所以：
题：输出拓扑序，若有多解输出字典序最小的那个（即尽量让小编号在前）。
关键：队列是先进先出，无法保证「当前可选点中最小的先出」。把 queue 换成小根堆 priority_queue<int, vector<int>, greater<int>>：每次取当前所有入度为 0 的点里编号最小的。
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
bool topoMin(int n) {
for (int i = 1; i <= n; i++)
if (indeg[i] == 0) q.push(i);
int cnt = 0;
while (!q.empty()) {
int u = q.top(); q.pop();
ans[++cnt] = u;
for (int v : g[u])
if (--indeg[v] == 0) q.push(v);
}
return cnt == n;
}DAG 有一个极好的性质：按拓扑序处理时，所有前驱都已经算完了。所以在拓扑序上做 DP，不需要记忆化，也不会重复计算。
f[v] = max(f[v], f[u] + 1)（每经过一条边长度 +1）// 假设已经求出 topo 数组
for (int i = 1; i <= n; i++) f[i] = 1; // 每个点自己至少长度为 1
for (int u : topo) {
for (int v : g[u]) {
f[v] = max(f[v], f[u] + 1);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, f[i]);这是 PDF 里的经典例题，难点全在「怎么建成图」。
建模：把每一场比赛（而不是球队）当成一个点。共有 N(N−1)/2 场比赛。
若某支球队的对手顺序是 a → b → c，说明「这场 (i,a) 必须在 (i,b) 之前打」，于是从 (i,a) 向 (i,b) 连一条有向边。
建完图后，同一支球队的比赛被串成了一条链，约束全部变成有向边。因为顺序不会自相矛盾，图一定是 DAG。
求什么：最少天数 = DAG 上最长路径的边数 + 1。用上面的拓扑 DP 求最长路即可。
复杂度：点数 O(N²)，边数 O(N²)，总复杂度 O(N²)。N ≤ 1000 时约 10⁶，可行。
关键一步：把「比赛」抽象成点，而不是把球队当点。这种「以边/事件为点」的建模在图论里很常见。
拓扑排序的模板只有 20 行，但它能解决的题非常多。下面 3 道题分别对应「判环」「字典序」「DAG 上 DP」三种典型考法。
共有 n 门课，给出 m 条先修关系 u v（学 v 之前必须先学 u）。判断是否存在一种顺序，能把这 n 门课全部学完。
输入：
4 4
1 2
2 3
3 4
4 2
输出：
NO
说明：2→3→4→2 构成环，这 3 门课互相依赖，永远学不完思路：跑一遍 Kahn 算法，统计成功弹出的点数 tot。若 tot == n 说明无环，否则环上那些点的入度永远减不到 0。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> e[N];
int indeg[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v);
indeg[v]++; // 建图时顺便统计入度
}
queue<int> q;
for (int i = 1; i <= n; i++)
if (indeg[i] == 0) q.push(i); // 所有「没有前置」的点先入队
int tot = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
tot++;
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i];
if (--indeg[v] == 0) q.push(v); // 前置全部完成，可以学了
}
}
puts(tot == n ? "YES" : "NO");
return 0;
}e[u].push_back(v) 记边，indeg[v]++ 记入度。入度不能事后单独算——那样要再扫一遍所有边，白费一次 O(m)。tot 永远小于 n，误判成有环。tot 数的是「成功弹出的点数」，不是边数、也不是轮数。它就是被排进拓扑序的点个数，最终与 n 比较。if (--indeg[v] == 0) 把「减一」和「判断」合成一句。这里必须先减再判，顺序不能反；写成 if(indeg[v]-1==0) indeg[v]--; 虽然也对，但两句容易写漏一句。tot < n——这就是拓扑排序判环的全部原理。tot == n。给定一个 DAG，输出字典序最小的拓扑序。即：在所有合法顺序里，第一个数尽量小；第一个数相同时，第二个数尽量小……以此类推。
输入：
5 4
1 3
2 3
3 4
3 5
输出：
1 2 3 4 5
说明：1 和 2 都无前置，但 1 < 2 所以先出 1；剩下的 2 也满足条件，接着出 2关键改动只有一行：把普通 queue 换成小根堆 priority_queue<int, vector<int>, greater<int>>。这样每次取出的都是「当前可选的、编号最小的」点，贪心结果就是字典序最小。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> e[N];
int indeg[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v); indeg[v]++;
}
// 小根堆：每次取编号最小的可选项
priority_queue<int, vector<int>, greater<int> > q;
for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.top(); q.pop();
printf("%d ", u);
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i];
if (--indeg[v] == 0) q.push(v);
}
}
return 0;
}int、底层容器 vector<int>、比较器 greater<int>。greater 表示「大的排后面」，于是堆顶最小。大于号后面必须空一格再写 > >，否则 >> 会被当成右移运算符——C++98 时代的经典坑（C++11 起已允许连写）。top() + pop() 取最小值，与普通队列的 front() 不同。堆没有 front，用错会编译失败。有 n 项工程，第 i 项耗时 t[i]。给出 m 条依赖 u v（u 完成后 v 才能开始）。工程可以并行进行，求整个项目的最短完工时间。
输入：
5 4
3 2 4 1 5
1 3
2 3
3 4
3 5
输出：
12
说明：1(3) 与 2(2) 并行；3 要等两者都完成，从时刻 3 开始跑到 7；
4 从 7 跑到 8，5 从 7 跑到 12。最长链 1→3→5 = 3+4+5 = 12思路：答案是「最长的那条依赖链」，即 DAG 上的最长路。设 f[v] 为「以 v 结尾的最长耗时」，转移为 f[v] = max(f[v], f[u] + t[v])。必须按拓扑序递推，才能保证算 f[v] 时所有前驱已经算好。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> e[N];
int indeg[N], t[N], f[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v); indeg[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++)
if (indeg[i] == 0) { f[i] = t[i]; q.push(i); } // 无前置的，自己就是起点
int ans = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
ans = max(ans, f[u]);
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i];
f[v] = max(f[v], f[u] + t[v]); // 所有前驱里取最大
if (--indeg[v] == 0) q.push(v);
}
}
printf("%d\n", ans);
return 0;
}t[i] 点权（耗时）、f[i] DP 值（以 i 结尾的最长耗时）、indeg[i] 入度。DP 值必须开在全局并初始化为 0，否则 max 会读到随机值。f[i] = t[i]：它没有前置，可以从时刻 0 直接开工，所以最早完成时间就是自己的耗时。这一步是 DP 的边界条件，漏了全盘皆 0。ans = max(ans, f[u]) 在出队时更新，而不是最后输出 f[n]。因为最长链未必结束在编号最大的点上——这是本题最容易错的一处。f[v] = max(f[v], f[u] + t[v])：v 的前驱可能有很多个，v 必须等最慢的那个完成，所以取 max 而不是 min。求最短路用 min，求工期/最长路用 max，一字之差题意完全不同。t[v] 而不是 t[u]：f[u] 已经包含 u 自己的耗时，我们正在算 v 的完成时刻，所以再加 v 的耗时。如果题目是边权（u→v 耗时 w），就改成 f[u] + w。f[v] 需要所有前驱都贡献过一次才能定下来，而 v 只有在入度归零时才入队——先更新再判入队，正好保证这一点。f[v] = max(f[u] + w)cnt[v] = Σ cnt[u]Floyd 只有 5 行，却是图论里性价比最高的算法：一次跑完，得到所有点对的距离。n ≤ 500 的多源最短路题，基本就是它。
多源最短路（全源最短路）：给定一张带权图，求任意两点 i、j 之间的最短距离。
如果对每个点各跑一次 Dijkstra，复杂度 O(n·m log m)，稠密图上很慢。Floyd 直接用 O(n³) 一次算完所有点对，而且允许负权边（但不能有负环）。
定义 f[k][i][j] = 从 i 到 j，且只允许经过编号 1..k 的点作为中转时的最短距离。
考虑第 k 个点用不用：
f[k−1][i][j]f[k−1][i][k] + f[k−1][k][j]（i 先到 k，再从 k 到 j）取较小值：
因为第 k 层只依赖第 k−1 层，可以把 k 这一维滚掉，直接在二维数组上原地更新，得到最终的三重循环。
const int N = 505;
const int INF = 0x3f3f3f3f;
int dis[N][N];
void floyd(int n) {
for (int k = 1; k <= n; k++) // 阶段：允许经过 1..k 中转
for (int i = 1; i <= n; i++) // 起点
for (int j = 1; j <= n; j++) // 终点
if (dis[i][k] != INF && dis[k][j] != INF)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}INF + INF 在 int 里会溢出成负数，可能导致错误更新。加一句判空更安全；也可以用 long long + 更大的 INF。const int INF = 0x3f3f3f3f; // 约 1.06e9，两个相加不爆 int
int dis[N][N];
int main() {
int n, m; cin >> n >> m;
// 1) 先把所有点对置为“不可达”，自己到自己为 0
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = (i == j ? 0 : INF);
// 2) 再读边（注意重边取 min！）
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
dis[u][v] = min(dis[u][v], w);
dis[v][u] = min(dis[v][u], w); // 无向图
}
floyd(n);
}dis[i][i] = 0 → 自己到自己变成 INFdis[u][v] = w → 后面的大权值覆盖了小权值memset(dis, 0x3f, ...) 后忘记把对角线清零0x3f3f3f3f ≈ 1.06×10⁹，两两相加 ≈ 2.1×10⁹，仍在 int 范围内INT_MAX（2.1×10⁹），加一下就溢出long long 和 1e18这是 Floyd 最容易被问、也最容易写错的地方。看看把 k 放到最内层会发生什么：
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);当 k 在最外层时，进入第 k 轮之前，dis[i][j] 已经是「只用 1..k−1 中转」的最优解，所以 dis[i][k]、dis[k][j] 也都是这一阶段的正确值，转移成立。
当 k 在最内层时，处理 (i,j) 这一对时，dis[i][k] 或 dis[k][j] 可能还没有被本轮（甚至后面几轮）优化过，用的是「半成品」数据，结果可能偏大。
因为 dis[i][j] 与 dis[j][i] 相互独立（各自用自己的状态转移），i、j 谁在外层不影响第 k 阶段的完整性。但 k 必须在最外层。
图：4 个点，边 1-2(3)、1-3(10)、2-3(4)、2-4(1)、3-4(2)。初始矩阵如下（INF 用 ∞ 表示）：
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 3 | 10 | ∞ |
| 2 | 3 | 0 | 4 | 1 |
| 3 | 10 | 4 | 0 | 2 |
| 4 | ∞ | 1 | 2 | 0 |
1-3 有直接边，权值 10，但显然绕 2 更短（3+4=7），Floyd 会把它优化掉。
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 3 | 3+4=7 | 3+1=4 |
| 2 | 3 | 0 | 4 | 1 |
| 3 | 4+3=7 | 4 | 0 | 2 |
| 4 | 1+3=4 | 1 | 2 | 0 |
1→3 变成 7（1→2→3），1→4 变成 4（1→2→4）。
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 3 | 7 | 7+2=9? |
| 2 | 3 | 0 | 4 | 1 |
| 3 | 7 | 4 | 0 | 2 |
| 4 | 4 | 1 | 2 | 0 |
1→4 尝试 1→3→4 = 7+2 = 9，但已经是 4（更小），所以保持不变。这说明 Floyd 只会「变小」，不会「变坏」。
把「最小距离」换成「布尔值」，min 换成 or，+ 换成 and：
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (reach[i][k] && reach[k][j])
reach[i][j] = 1;用来求「两点间是否连通」「图的连通性」等。
枚举中转点 k 时，先用「只经过 1..k−1」的路径拼出一个经过 k 的环：
for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++)
for (int j = i + 1; j < k; j++)
ans = min(ans, dis[i][j] + w[i][k] + w[k][j]);
// 再执行正常的 Floyd 转移
}关键：先算环，再更新 dis，否则会用同一条边两次。
Floyd 的代码只有 5 行，但「循环顺序」「初始化」「INF 选择」三个坑能让人 WA 一整场。下面 3 道题分别练最短路、传递闭包、最小环。
n 个点、m 条无向带权边（权值为正），有 q 次询问，每次给 u v，求 u 到 v 的最短距离，不可达输出 -1。
输入：
4 4
1 2 3
2 3 4
1 3 10
3 4 2
3
1 3
1 4
2 4
输出：
7
9
6为什么选 Floyd：n ≤ 300 → n³ = 2.7×10⁷，一秒内轻松跑完；而「多次询问任意两点」正是 Floyd 的主场——预处理一次，之后每次询问 O(1)。若改用 Dijkstra 跑 n 次，是 O(n·m log m)，在稠密图上反而更慢。
#include <bits/stdc++.h>
using namespace std;
const int N = 305, INF = 0x3f3f3f3f;
int dis[N][N];
int main() {
int n, m; scanf("%d%d", &n, &m);
memset(dis, 0x3f, sizeof dis); // ① 全部置 INF
for (int i = 1; i <= n; i++) dis[i][i] = 0; // ② 自己到自己为 0
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
dis[u][v] = min(dis[u][v], w); // ③ 重边取最小
dis[v][u] = min(dis[v][u], w); // 无向图双向
}
for (int k = 1; k <= n; k++) // k 必须在最外层！
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dis[i][k] + dis[k][j] < dis[i][j])
dis[i][j] = dis[i][k] + dis[k][j];
int q; scanf("%d", &q);
while (q--) {
int u, v; scanf("%d%d", &u, &v);
printf("%d\n", dis[u][v] == INF ? -1 : dis[u][v]);
}
return 0;
}memset(dis, 0x3f, sizeof dis) 把每个字节填成 0x3f，一个 int 四个字节就变成 0x3f3f3f3f = 1061109567。它有两个好处：足够大（约 10⁹）、且两个相加不会超过 int 上限（2×10⁹ < 2.1×10⁹），所以 dis[i][k] + dis[k][j] 不会溢出。dis[i][i] = 0 绝不能漏。漏了会怎样？自己到自己变成 INF，于是任何经过自己中转的路径都不会被采用，甚至 dis[i][k] + dis[k][i] 这种「走一圈回来」的更新会把矩阵改得面目全非。dis[u][v] = w 会让最后输入的那条生效，而不是最小的那条。dis[k][i][j] 表示「只允许经过编号 ≤ k 的点时 i 到 j 的最短距离」。算第 k 阶段必须先有完整的第 k−1 阶段，所以 k 只能放最外层。dis[i][k] + dis[k][j] < dis[i][j] 的物理含义：从 i 先到 k、再从 k 到 j，若比现在更短就更新。这就是「绕一下 k 会不会更划算」。== INF。注意只能判等号，不能判 >= INF——因为 INF 被赋值过之后不会再变，用等号最精确。int d = dis[i][k]; 先把值取出来，避免每次访问二维数组：if (d + dis[k][j] < dis[i][j]) dis[i][j] = d + dis[k][j];。n = 300 时差别不大，n = 500 时能快 20% 左右。另外若 d == INF 可直接 continue 跳过整行。给定有向图，对每个点 i 求「从 i 出发能到达多少个不同的点」（不含 i 自己）。
输入：
4 3
1 2
2 3
4 3
输出：
2 1 0 1
说明：1 能到 {2,3}；2 能到 {3}；3 谁也到不了；4 能到 {3}思路：把「距离」换成「能否到达」，Floyd 就能算传递闭包：r[i][j] = true 表示 i 能到 j，转移式变成 r[i][j] |= r[i][k] & r[k][j]。n 只有 300，O(n³) = 2.7×10⁷，完全够。
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
bool r[N][N]; // r[i][j]：i 能否到达 j
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
r[u][v] = true; // 有向边
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
if (r[i][k]) // 剪枝：i 到不了 k 就不用试
for (int j = 1; j <= n; j++)
if (r[k][j]) r[i][j] = true;
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++)
if (j != i && r[i][j]) cnt++;
printf("%d ", cnt);
}
return 0;
}bool 二维数组，只关心「通不通」不关心「多远」。空间 n² = 9×10⁴ 字节，几乎不占内存。r[u][v] = true，不给对角线置真。这题的「可达」不含自己，如果给 r[i][i] 置真，最后统计时要额外减去。两种做法都对，关键是想清楚自己要哪一种。if (r[i][k]) 是重要剪枝：i 都到不了 k，就别指望「i→k→j」了，直接跳过整个内层循环。在稀疏的可达图上这一句能省掉 80% 以上的无效循环。r[i][j] = true，不需要 |=。因为一旦为真就永远为真，直接赋值即可。（若用整型数组则要写 r[i][j] |= r[i][k] & r[k][j]。）j != i 排除自己。如果题目改成「含自己」，把这个条件删掉即可——先看清题目要求再写统计。bitset<2000> r[2000]，转移写成 if (r[i][k]) r[i] |= r[k];——一次操作处理 64 位，复杂度降到 O(n³/64) ≈ 1.25×10⁸，就能过了。这是「传递闭包」的标准优化写法。求无向带权图中权值和最小的环。环至少要包含 3 个点（重边构成的 2 点环按题目约定通常不算）。若没有环输出 -1。
输入：
4 5
1 2 1
2 3 1
3 1 1
3 4 1
4 1 5
输出：
3
说明：1-2-3-1 权值和 1+1+1 = 3；1-3-4-1 是 1+1+5 = 7。取 3思路（Floyd 的经典副产品）：在 Floyd 进行到第 k 轮之前，dis[i][j] 表示「只经过编号 < k 的点」时 i 到 j 的最短路。此时选一条 i→k→j 的路径再接上 dis[i][j]，就构成一个以 k 为最大编号点的环，长度为 dis[i][j] + g[i][k] + g[k][j]。把所有 k、i、j 都枚举一遍就能拿到最小环。
#include <bits/stdc++.h>
using namespace std;
const int N = 305, INF = 0x3f3f3f3f;
int g[N][N], dis[N][N];
int main() {
int n, m; scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i++) g[i][i] = 0;
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
g[u][v] = min(g[u][v], w);
g[v][u] = min(g[v][u], w);
}
memcpy(dis, g, sizeof g); // dis 是 g 的副本，会不断被优化
int ans = INF;
for (int k = 1; k <= n; k++) {
// 第一步：用「不经过 k」的最短路 + 两条到 k 的边，拼出环
for (int i = 1; i < k; i++)
for (int j = i + 1; j < k; j++)
if (g[i][k] != INF && g[k][j] != INF && dis[i][j] != INF)
ans = min(ans, dis[i][j] + g[i][k] + g[k][j]);
// 第二步：再让 k 参与最短路更新
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dis[i][k] + dis[k][j] < dis[i][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
printf("%d\n", ans == INF ? -1 : ans);
return 0;
}g 存原始边（永不被修改，用来取 g[i][k] 这条真实边），dis 存最短路（会被 Floyd 不断优化）。如果只用一个矩阵，取 g[i][k] 时可能拿到一条「绕路」的路径而不是直连边，环就拼错了。memcpy(dis, g, sizeof g) 复制整个二维数组。不能写 dis = g（数组不能赋值），也不能只复制有效区域（用 sizeof 最简单不易错）。dis[i][j] 已经可能经过了 k，再拼 i→k→j 就会重复经过同一个点，拼出来的不是简单环。i < k、j < k 的循环界：我们约定「k 是环上编号最大的点」，所以另外两个点只能小于 k。同时 j 从 i+1 开始，避免同一个环被算两次（i→j 和 j→i）。dis[i][j] + g[i][k] + g[k][j]：中间一段是 i 到 j 的最短路（不经过 k），两头各接一条真实边。三处都要判 != INF，否则 INF 相加会溢出成负数，反而被当成最小值选中。ans == INF 说明一个环都没找到。无环图（比如一棵树）就会走到这里，按题目要求输出 −1。dis 表示「只允许前 k−1 个点作中转」，这个「阶段性」正好可以用来构造「以 k 为最大点」的结构。类似技巧还有「Floyd 求最小环」「Floyd 求恰好 k 条边的最短路（矩阵快速幂）」。Floyd 求「任意两点」，但复杂度 O(n³) 只扛得住 n ≤ 500。真实题目动辄 n = 10⁵，这时必须换 Dijkstra：只从一个起点出发，O(m log m) 跑完。它是 CSP-J/S 复赛出现频率最高的图论算法，没有之一。
单源最短路（Single Source Shortest Path, SSSP）：给定一个起点 s（叫「源点」），求 s 到每一个其他点的最短距离。
| 算法 | 解决什么 | 复杂度 | 负权边 | 典型数据范围 |
|---|---|---|---|---|
| Floyd | 任意两点 | O(n³) | 可以 | n ≤ 500 |
| Dijkstra 朴素 | 单源 | O(n²) | 不行 | n ≤ 5000，稠密图 |
| Dijkstra 堆优化 | 单源 | O(m log m) | 不行 | n ≤ 10⁵，稀疏图 |
| Bellman-Ford | 单源 | O(nm) | 可以 | n·m ≤ 10⁷ |
| SPFA | 单源 + 判负环 | 平均 O(km)，最坏 O(nm) | 可以 | 随机数据 |
Dijkstra 的核心只有一个信念：
dis 值最小的那个点，它的最短路已经确定了，不可能再被别的路径改小。为什么敢这么说？因为边权非负。假设当前 dis[u] 是所有未确定点里最小的。如果还存在一条更短的路径能从 s 到 u，那它必须先经过某个未确定的点 x，而 dis[x] ≥ dis[u]，再加上从 x 到 u 的边权 w ≥ 0，总长 ≥ dis[u]，不可能更短。矛盾。
所以每个点一旦被「选中」，它的 dis 就永久固定，可以放心拿它去更新别人。这正是贪心 + 松弛（relax） 的组合。
先看慢但最好懂的版本。适合 n ≤ 5000 的稠密图（边数接近 n²）。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
const int INF = 0x3f3f3f3f;
int n, m, s;
int g[N][N]; // 邻接矩阵，g[u][v] = 边权，无边为 INF
int dis[N]; // dis[i]：s 到 i 的当前最短距离
bool vis[N]; // vis[i]：i 是否已进入 S 集合
void dijkstra(int s) {
memset(dis, 0x3f, sizeof dis); // 全部置为 0x3f3f3f3f
dis[s] = 0; // 起点到自己是 0，千万别漏！
for (int i = 1; i <= n; i++) { // 循环 n 轮，每轮确定一个点
// 第 1 步：在未确定的点里找 dis 最小的那个 u
int u = -1;
for (int j = 1; j <= n; j++)
if (!vis[j] && (u == -1 || dis[j] < dis[u])) u = j;
if (u == -1 || dis[u] == INF) break; // 剩下的点都不可达，提前结束
vis[u] = true; // 第 2 步：u 的最短路确定了，加入 S
// 第 3 步：用 u 松弛所有邻居
for (int v = 1; v <= n; v++) {
if (g[u][v] != INF && dis[u] + g[u][v] < dis[v])
dis[v] = dis[u] + g[u][v];
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &s);
memset(g, 0x3f, sizeof g); // 矩阵初始化成 INF
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
g[u][v] = min(g[u][v], w); // 有重边时取最小的那条
g[v][u] = min(g[v][u], w); // 无向图才要这一行！有向图删掉
}
dijkstra(s);
for (int i = 1; i <= n; i++)
printf("%d ", dis[i] == INF ? -1 : dis[i]);
return 0;
}N 是点上限，INF 取 0x3f3f3f3f（约 1.06×10⁹）。为什么不用 1e9？因为 memset 只能按字节填充，只有「每字节 0x3f」才能用 memset 一次性刷出这个值。g 邻接矩阵（n² 个 int，n=5000 时约 100MB，这已是邻接矩阵的上限）、dis 当前最短距离、vis 是否已确定。全局数组默认全 0，所以 dis 必须手动刷 INF。memset(dis, 0x3f) 把所有点设为「不可达」，dis[s] = 0 把起点设为 0。第二句写成 dis[1] = 0 是最常见的错——起点不是 1 号点时全错。u == -1 || 这个短路条件很关键。第一轮 u 是 −1，直接取 j；之后才有 dis[u] 可比较。写成 dis[j] < dis[u] 而不加保护，第一次就会访问 dis[-1]，读越界内存。!vis[j] 不能省。省了的话已确定的点会一直被选中，算法在几个点之间原地打转，永远出不来。dis[u] == INF 说明剩下的点全都不可达，继续跑没有意义。这一句能省时间，也能避免 INF + w 溢出。vis[u] = true 就是「把 u 放进 S 集合」，代表它的最短路已永久确定。整个算法的贪心就体现在这一句。g[u][v] != INF（确实有边）且 dis[u]+g[u][v] < dis[v]（绕 u 更近）。只判后者时，无边的情况会算出 INF + INF 溢出成负数，把 dis 改成一个荒谬的小值。g[u][v] = min(g[u][v], w)，直接赋值会取到后输入的那条dis[s]=0 写成 dis[1]=0（起点不是 1 就错）g[v][u] 反向边，答案偏小dis[u] == INF 不判断，INF + w 溢出成负数复杂度：外层 n 轮，内层两次 n——找最小 O(n)、松弛 O(n)，合计 O(n²)。与边数无关，所以稠密图（m ≈ n²）非常划算；但稀疏图（m ≈ n）就白白浪费了。
下面这张无向图，求 1 号点到所有点的最短距离。请拿纸笔跟着推一遍，这是理解 Dijkstra 最快的方式。
| 轮次 | dis[1] | dis[2] | dis[3] | dis[4] | dis[5] | 本轮选中 |
|---|---|---|---|---|---|---|
| 初始 | 0 | ∞ | ∞ | ∞ | ∞ | — |
| 1 | 0 | 2 | 5 | ∞ | ∞ | 1 |
| 2 | 0 | 2 | 3 | 8 | ∞ | 2 |
| 3 | 0 | 2 | 3 | 5 | 11 | 3 |
| 4 | 0 | 2 | 3 | 5 | 8 | 4 |
| 5 | 0 | 2 | 3 | 5 | 8 | 5 |
绿色 = 已确定（进 S），粉色 = 本轮被松弛改小的值，黄色 = 本轮选中的点。
朴素版最耗时的部分是「在未确定的点里扫一遍找最小」，每轮 O(n)，总共 O(n²)。但如果我们用一个小根堆（优先队列）把候选点按 dis 排序，取最小就变成 O(1)，插入 O(log m)。
配套必须换成 邻接表——因为松弛时只需要遍历真实存在的边，不再扫 n 个不存在的点。总复杂度 O(m log m)，n = 10⁵、m = 2×10⁵ 轻松跑过。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector<Edge> e[N]; // e[u] 存 u 的所有出边
int dis[N];
bool vis[N]; // vis[u]：u 是否已经从堆里「正式取出」过
void dijkstra(int s, int n) {
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
// 小根堆：pair 默认先比 first，所以必须把 dis 放在 first
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0, s}); // {距离, 点编号}
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue; // 关键！同一个点可能入堆多次，旧的直接扔掉
vis[u] = true;
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
q.push({dis[v], v}); // 不删旧值，直接塞新的
}
}
}
}vector<Edge> e[N] 就是「N 个可变长列表」，写法比前向星简单，速度略慢但够用。vis 在堆优化里的语义变了：不再是「在 S 集合里」，而是「这个点已经正式处理过了」。因为堆里会有重复记录，需要这个标记来跳过旧的。pair<int,int>、底层 vector、比较器 greater。pair 默认先比 first，所以必须把距离放 first、点编号放 second，写反了就变成按编号排序，堆彻底失效。second 当点编号，因为 first 是距离。q.top() 取堆顶（最小值），q.pop() 之后再访问 top() 就已经是下一个了——这两句顺序不能反。if (vis[u]) continue; 是整个堆优化版本的灵魂。同一个点可能被 push 多次（每次变优都塞一条），旧的那条弹出来时必须扔掉。删掉这一句，代码不但变慢，还可能用过期距离去松弛邻居，答案出错。e[u].size() 要转 (int) 避免无符号比较警告；e[u][i].to 和 .w 分别取终点和边权。dis[v]（刚更新后的值），不是 dis[u]+w 的表达式——虽然数值相同，但读 dis[v] 更不容易写错。{8, 3} 和 {5, 3} 两条记录。因为是小根堆，{5,3} 一定先弹出，此时 vis[3]=true；等 {8,3} 弹出来时被 if (vis[u]) continue; 直接跳过。所以 vis 判重不是可选项，是必须的——去掉它，算法不仅变慢，还可能把已经确定的值改错。priority_queue<pair<int,int>, vector<...>, greater<...>>q.push({-dis[v], v})，用默认大根堆operator<，注意方向是反的dis 换 long long，INF 换 0x3f3f3f3f3f3f3f3f6.2 的证明用了一句话：「从 x 到 u 的边权 w ≥ 0」。如果把这条前提拿掉，整个贪心就塌了。看下面这个反例。
正确答案：A→B 走 A→C→B = 2 + (−3) = −1，比直接走 A→B 的 1 更短；A→D 走 A→C→B→D = −1 + 1 = 0，比 A→B→D 的 2、A→C→D 的 7 都短。
Dijkstra 会怎么算：
vis[B]=true，B 被永久确定成 1最终 Dijkstra 给出 dis[B]=1、dis[D]=2，全部错。根因就是第 2 步：它在「还不知道 C 的情况」时就把 B 定死了。
思路：n 高达 10⁵，Floyd 和朴素 Dijkstra 都会 TLE，必须用堆优化 + 邻接表（或链式前向星）。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 200005;
const int INF = 0x3f3f3f3f;
int head[N], nxt[M], to[M], wt[M], tot;
int n, m, s, dis[N];
bool done[N];
void add(int u, int v, int c) {
to[++tot] = v; wt[tot] = c; nxt[tot] = head[u]; head[u] = tot;
}
int main() {
memset(head, -1, sizeof head);
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
int u, v, c; scanf("%d%d%d", &u, &v, &c);
add(u, v, c); // 有向图：只加一条！
}
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0, s});
while (!q.empty()) {
int d = q.top().first, u = q.top().second;
q.pop();
if (done[u]) continue;
done[u] = true;
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = to[i];
if (d + wt[i] < dis[v]) {
dis[v] = d + wt[i];
q.push({dis[v], v});
}
}
}
for (int i = 1; i <= n; i++)
printf("%d ", dis[i]);
return 0;
}输入：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出：
0 2 4 3核对：1→3 最短路是 1→2→3 = 4（比直达的 5 短）；1→4 是 1→2→4 = 3（比直达的 4 短）。可见「直达不一定最短」，这正是松弛存在的意义。
%d 且按题意不可达保留 0x3f3f3f3f（部分版本要求输出 2³¹−1 = 2147483647，与 0x3f3f3f3f 数值相同，天然吻合）。如果边权开到 10⁹，一定换 long long。暴力想法：从每个急救站各跑一次 Dijkstra，复杂度 O(k·m log m)，k 接近 n 时直接爆炸。
正解：建一个「超级源点」。想象一个虚拟点 0，它到每个急救站都有一条权值为 0 的边。那么「0 到 v 的最短路」就等于「离 v 最近的急救站到 v 的距离」。实现上甚至不用真的建点 0——把 k 个急救站同时压进堆，dis 全部初始化为 0即可。
// 与单源完全一样，只改初始化部分
memset(dis, 0x3f, sizeof dis);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
for (int i = 1; i <= k; i++) {
int x; scanf("%d", &x); // 读入一个急救站编号
dis[x] = 0; // 源点自己到自己是 0
q.push({0, x}); // 全部先塞进堆
}
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
// 结束后 dis[i] 就是 i 到最近急救站的时间初始：dis[1]=∞, dis[2]=0, dis[3]=∞；堆 = {(0,2)}
弹 2 → dis[1]=4, dis[3]=7
弹 1（4）→ 无更优
弹 3（7）→ 无更优
结果：dis[1]=4, dis[2]=0, dis[3]=7Dijkstra 是复赛出现频率最高的图论算法。下面 3 道题覆盖了「模板题」「多源改造」「计数变形」三种考法，建议每道都手写一遍到不看模板为止。
给定 n 个点、m 条有向边，边权为正整数，求起点 s 到每个点的最短距离。不可达输出 -1。
输入：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出：
0 2 4 3这道题的唯一难点是溢出：边权可达 10⁹，路径上最多 10⁵ 条边，最短路最长可达 10¹⁴，int 上限只有 2.1×10⁹，会在中途变成负数。所以距离数组、堆元素、INF 全部要用 long long。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
struct Edge { int to; long long w; };
vector<Edge> e[N];
long long dis[N];
int main() {
int n, m, s; scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
int u, v; long long w;
scanf("%d%d%lld", &u, &v, &w);
e[u].push_back({v, w}); // 有向图：只加一条
}
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
typedef pair<long long,int> PLI;
priority_queue<PLI, vector<PLI>, greater<PLI> > q;
q.push({0, s});
while (!q.empty()) {
PLI cur = q.top(); q.pop();
long long d = cur.first; int u = cur.second;
if (d > dis[u]) continue; // 懒惰删除：过期的直接扔
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to; long long w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
for (int i = 1; i <= n; i++)
printf("%lld ", dis[i] == INF ? -1 : dis[i]);
return 0;
}0x3f3f3f3f3f3f3f3fLL 是 long long 版的 INF，约 4.6×10¹⁸。它同样是「每字节 0x3f」的产物，所以 memset(dis, 0x3f, ...) 能直接填出这个值。别写 1e18——那样 memset 就不管用了。w 也必须是 long long。如果只把 dis 改成 long long、w 还是 int，读入 10⁹ 没问题，但 dis[u] + w 里 w 会先参与提升，问题不大；真正致命的是把 w 读进 int 变量时若超过 2.1×10⁹ 就越界了。typedef pair<long long,int> PLI 简化类型名。堆的模板参数写全了太长，用 typedef 之后 priority_queue<PLI, vector<PLI>, greater<PLI>> 清爽很多。first 放进 d、second 放进 u，不要反复写 q.top().first。注意 d 是 long long，若写成 int 就白改了。if (d > dis[u]) continue; 是懒惰删除：同一个点可能入堆多次（每次变优都塞一条），堆里会有 (8,3) 和 (5,3)。弹出 (5,3) 时 dis[3] 已是 5，正常处理；之后弹出 (8,3) 时 8 > 5，直接扔掉。它等价于 if(vis[u]) continue;，但不需要额外开 vis 数组。dis[v]，不是旧的。%lld 与 long long 配对，并且用 == INF 判不可达。三个 long long 相关的细节（INF、堆元素、输出格式）任何一个漏了，都会得到莫名其妙的负数输出。dis 数组；② 堆的 pair 第一个元素；③ INF 常量。只改其中一两个，错误会以「输出负数」的形式出现，而且很难一眼看出。看到边权 10⁹ 就直接全套 long long，不要省。n 个村庄、m 条双向公路（边权为通行时间），其中 k 个村庄建有医院。求每个村庄到最近医院的最短时间。
输入：
5 4 2
1 2 7
2 3 5
3 4 1
4 5 3
2 4
输出：
7 0 1 0 3
说明：3 号村离 2 号医院 5、离 4 号医院 1，取 1暴力思路：从每个医院各跑一次 Dijkstra，O(k·m log m)，k 接近 n 时直接爆炸。
正解：想象一个「超级源点 0」，它到每个医院都有一条权值为 0 的边。那么「0 到 v 的最短路」正好就是「离 v 最近的医院到 v 的距离」。实现上不用真的建点 0——把 k 个医院同时压进堆、dis 全设 0 即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
struct Edge { int to; long long w; };
vector<Edge> e[N];
long long dis[N];
int main() {
int n, m, k; scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int u, v; long long w;
scanf("%d%d%lld", &u, &v, &w);
e[u].push_back({v, w});
e[v].push_back({u, w}); // 双向公路
}
memset(dis, 0x3f, sizeof dis);
typedef pair<long long,int> PLI;
priority_queue<PLI, vector<PLI>, greater<PLI> > q;
for (int i = 1; i <= k; i++) {
int x; scanf("%d", &x);
dis[x] = 0; // 医院自己距离 0
q.push({0, x}); // 全部先入堆
}
while (!q.empty()) {
PLI cur = q.top(); q.pop();
long long d = cur.first; int u = cur.second;
if (d > dis[u]) continue;
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to; long long w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
for (int i = 1; i <= n; i++) printf("%lld ", dis[i]);
return 0;
}dis[x] = 0、q.push({0, x})、以及循环 k 次。后面的 Dijkstra 主体一个字都不用改——这就是「最小改动解决新问题」的典型。dis[i]，不需要判 INF——题目保证每个村庄都至少能到一个医院。若不能保证，就要加 dis[i]==INF?-1:dis[i]。求从 1 号点到 n 号点有多少条不同的最短路径。边权均为 1，答案对 1000000007 取模。
输入：
4 5
1 2 1
2 4 1
1 3 1
3 4 1
1 4 3
输出：
2
说明：1-2-4 与 1-3-4 长度都是 2，是最短的，共 2 条思路：在松弛时多维护一个 cnt[]。遇到严格更短的路径，cnt[v] = cnt[u]（旧路径全作废）；遇到长度相等的路径，cnt[v] += cnt[u]（累加方案数）。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, MOD = 1000000007, INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector<Edge> e[N];
int dis[N], cnt[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
e[u].push_back({v, w});
e[v].push_back({u, w});
}
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
cnt[1] = 1; // 起点到自己有 1 条（空路径）
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > q;
q.push({0, 1});
while (!q.empty()) {
pair<int,int> cur = q.top(); q.pop();
int d = cur.first, u = cur.second;
if (d > dis[u]) continue;
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u]; // 更短了，方案数重置
q.push({dis[v], v});
} else if (dis[u] + w == dis[v]) {
cnt[v] = (cnt[v] + cnt[u]) % MOD; // 一样短，累加
}
}
}
printf("%d\n", dis[n] == INF ? 0 : cnt[n]);
return 0;
}long long：边权是 1、n ≤ 2×10⁵，最短路最大 2×10⁵，int 完全够。数据范围决定类型，不要无脑 long long（会变慢）。cnt[1] = 1 是 DP 的边界：从 1 到 1 有 1 条「空路径」。如果写成 0，后面所有累加都是 0，最终答案永远是 0——这是本题第一个必错点。vis 数组，只有懒惰删除。因为「相等距离」时还要继续累加计数，若像 P6-1 那样一旦出堆就标记 vis 并跳过，会漏掉后半段相等的方案。计数题的 Dijkstra 不能加 vis。cnt[v] = cnt[u]（赋值，不是累加）。因为之前算出的所有路径都比现在这条长，全部作废，方案数直接继承 u 的。cnt[v] += cnt[u]。两条不同路径都达到同样的最短长度，所以方案数相加。这句是本题的核心，用 else if 而不是独立的 if，避免前后矛盾。cnt 会被重复累加（同一批方案被算多次）。要处理这种情况必须按拓扑序传播，非常麻烦。计数一律用 Dijkstra——按距离从小到大处理，天然保证每个状态只被最终确定一次。| 要点 | 必须记住的内容 |
|---|---|
| 适用条件 | 单源、边权全部非负。有负权 → 换 SPFA / Bellman-Ford |
| 贪心核心 | 未确定点中 dis 最小的那个，最短路已确定，可永久固定 |
| 松弛 | if (dis[u]+w < dis[v]) dis[v] = dis[u]+w; 一切最短路的统一动作 |
| 两套模板 | 朴素 O(n²)（邻接矩阵，稠密图）／堆优化 O(m log m)（邻接表，稀疏图） |
| 必写四句 | dis[s]=0、dis 置 INF、if(vis[u]) continue、堆按距离排序 |
| 常见变体 | 多源（全部入堆）、反向建图、加维度做分层图 |
Dijkstra 死在负权边上。这一章的两个算法专门对付「边权可能为负」的图，并且顺带解决一个更难的问题：图里有没有负环。最后用「分层图」把最短路技巧推到能解带限制的题。
纯「路程、时间、花费」不会为负。但下面这些建模会出现负权：
走一条商路赚 5，走另一条亏 3。把「赚」记作负权、「亏」记作正权，求总成本最小。
A→B 收费 10，B→A 返 4。反向边权值就是 −4。
x_v − x_u ≥ w 这类不等式组，可转成 u→v 边权 −w 的最短路问题。
核心洞察只有一句：
于是算法极其朴素：做 n−1 轮，每轮把所有边都拿来试一次松弛。第 1 轮结束后，最多 1 条边的最短路全部正确；第 2 轮结束后，最多 2 条边的全部正确……第 n−1 轮结束后，所有最短路都正确。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005, M = 6005, INF = 0x3f3f3f3f;
struct Edge { int u, v, w; } E[M]; // 只需要「边表」，不用邻接结构
int n, m, s, dis[N];
bool bellman(int s) { // 返回 true 表示存在负环
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
for (int i = 1; i < n; i++) { // 最多 n-1 轮
bool updated = false;
for (int j = 1; j <= m; j++) {
int u = E[j].u, v = E[j].v, w = E[j].w;
if (dis[u] != INF && dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
updated = true;
}
}
if (!updated) break; // 一轮下来没有任何变化 → 已经收敛，提前退出
}
// 第 n 轮：如果还能松弛，说明存在负环
for (int j = 1; j <= m; j++) {
int u = E[j].u, v = E[j].v, w = E[j].w;
if (dis[u] != INF && dis[u] + w < dis[v]) return true;
}
return false;
}
int main() {
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
// 无向图要把每条边拆成两条：E[++m] = {v,u,w}; 记得 m 先翻倍
}
if (bellman(s)) puts("存在从 s 可达的负环");
else for (int i = 1; i <= n; i++) printf("%d ", dis[i]);
return 0;
}没有负环时，n−1 轮之后所有最短路都定下来了，第 n 轮不可能再有任何边能松弛成功。反过来，如果第 n 轮还能松弛——说明存在一条至少含 n 条边且比现有答案更短的路径。
n 个点的简单路径最多 n−1 条边。含 n 条边且还在变短，唯一解释就是路径里绕了环，而且这个环的权值之和是负数。由于每绕一圈都能让距离更小，这个点的最短路实际上不存在（可以无限变小）。
Bellman-Ford 的一大半工作是无用功：某个点 dis 没变，用它的边去松弛别人也不会变。于是有人想：只有 dis 刚刚被改小的点，才值得拿它的出边去松弛邻居。用队列维护这些「值得扩散」的点，就是 SPFA（Shortest Path Faster Algorithm）。
它的形状和 BFS 几乎一样，只是「一个点可以多次入队」。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector<Edge> e[N];
int dis[N];
bool inq[N]; // inq[u]：u 是否已在队列里（防止重复入队）
void spfa(int s) {
memset(dis, 0x3f, sizeof dis);
memset(inq, 0, sizeof inq);
dis[s] = 0;
queue<int> q;
q.push(s);
inq[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false; // 出队后必须清标记，允许它以后再次入队
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
if (!inq[v]) { // 已在队里就不重复塞
q.push(v);
inq[v] = true;
}
}
}
}
}e、距离 dis、inq（是否在队列中）。注意这里没有 vis——SPFA 允许一个点反复入队，不存在「永久确定」的概念。dis[s] = 0。第二句容易被忽略——如果 inq 残留 true，起点可能永远不会再入队。inq[u] = false 是 SPFA 最不能漏的一行。出队就清标记，这样它以后被更短的路径发现时还能再进来。漏了这句，SPFA 退化成「每个点只扩展一次」的 BFS，负权带来的二次优化全部丢失，答案错。dis[u] + w < dis[v] 就更新。区别在于「谁来算」——Dijkstra 用堆保证按距离顺序，SPFA 用队列反复试。inq 就是用来做这个去重的。dis[v] < dis[队首] 就插到队头（用 deque），常数更小。② LLL：把 dis[v] 与队内平均值比较。两者都能提速，但改变不了最坏复杂度，别指望靠它们过恶意数据。SPFA 判负环比 Bellman-Ford 优雅得多。维护 cnt[v] 表示「当前这条最短路用了几条边」：每次用 u 松弛 v 成功时，cnt[v] = cnt[u] + 1。一旦 cnt[v] ≥ n，说明最短路已经用了 n 条边——n 个点不可能有 n 条边的简单路径，必然绕了负环。
int cnt[N];
bool inq[N];
bool spfa_neg(int n) {
memset(dis, 0x3f, sizeof dis);
memset(inq, 0, sizeof inq);
memset(cnt, 0, sizeof cnt);
queue<int> q;
// 重要：把所有点都先入队并把 dis 置 0
// 这样才能检测「不与起点连通」的负环
for (int i = 1; i <= n; i++) {
dis[i] = 0;
q.push(i);
inq[i] = true;
}
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false;
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return true; // 负环！
if (!inq[v]) { q.push(v); inq[v] = true; }
}
}
}
return false;
}dis[s]=0，其余保持 INF；cnt 一定要在松弛成功时更新，不能放在入队处，否则统计的不是路径边数。
有一类题长这样：「你有 k 次免费通行的机会，求最小花费」。这时候单靠 dis[u] 不够用了——同一个点，用掉 0 次免费和用掉 1 次免费，是两个不同的状态。
做法：把状态写成二维 dis[u][j]，表示「到达 u，已经用掉 j 次免费机会」的最小花费。整张图实际上变成了 (k+1) 层，每层是原图的一份拷贝，层与层之间用「免费边」连接——这就是分层图。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005, K = 12, INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector<Edge> e[N];
struct Node {
int d, u, j;
bool operator<(const Node& o) const { return d > o.d; } // 反过来写 = 小根堆
};
int dis[N][K]; // dis[u][j]：到 u，已用 j 次免费
bool vis[N][K];
int n, m, k, s, t;
int solve() {
memset(dis, 0x3f, sizeof dis);
dis[s][0] = 0;
priority_queue<Node> q;
q.push({0, s, 0});
while (!q.empty()) {
Node cur = q.top(); q.pop();
int u = cur.u, j = cur.j;
if (cur.d > dis[u][j]) continue; // 懒惰删除
for (int i = 0; i <(int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
// 转移 1：正常走，付费
if (dis[u][j] + w < dis[v][j]) {
dis[v][j] = dis[u][j] + w;
q.push({dis[v][j], v, j});
}
// 转移 2：这一条免费走，层数 +1
if (j < k && dis[u][j] < dis[v][j + 1]) {
dis[v][j + 1] = dis[u][j];
q.push({dis[v][j + 1], v, j + 1});
}
}
}
int ans = INF;
for (int j = 0; j <= k; j++) ans = min(ans, dis[t][j]);
return ans;
}(u, j) 当成新图的顶点后，新图的边权依然全部非负（0 也非负），所以 Dijkstra 的正确性原封不动搬过来。这也是分层图最常用的实现方式。思路：只把 1 号点入队，dis[1]=0，其余保持 INF。这样能保证检测到的负环一定是从 1 可达的。用 cnt[v] ≥ n 判定。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005, INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector<Edge> e[N];
int dis[N], cnt[N];
bool inq[N];
bool hasNegCycle(int n) {
memset(dis, 0x3f, sizeof dis);
memset(cnt, 0, sizeof cnt);
memset(inq, 0, sizeof inq);
queue<int> q;
dis[1] = 0;
q.push(1);
inq[1] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false;
for (int i = 0; i <(int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return true;
if (!inq[v]) { q.push(v); inq[v] = true; }
}
}
}
return false;
}
int main() {
int T; scanf("%d", &T);
while (T--) {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) e[i].clear();
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
e[u].push_back({v, w});
// 注意：本题不同版本对建边约定的描述略有差别，
// 有的版本规定 w >= 0 要额外加一条反向边 v->u（权 w）。
// 一律以题目原文为准，别照抄记忆里的模板。
}
puts(hasNegCycle(n) ? "YE5" : "N0");
}
return 0;
}YE5（数字 5）和 N0（数字 0），不是 YES / NO；负权题的关键不在代码，而在判断：读题时能不能意识到「这里有负数」。下面 3 道题分别练 SPFA 求最短路、SPFA 判负环、分层图建模。
给定有向图，边权可以为负（数据保证不存在从 s 可达的负环），求 s 到各点的最短距离，不可达输出 1000000000。
输入：
4 5 1
1 2 2
2 3 -1
1 3 4
3 4 2
2 4 10
输出：
0 2 1 3
说明：1→3 走 1→2→3 = 2+(−1) = 1，比直达的 4 更短为什么不能用 Dijkstra：它假设「当前最小的 dis 已经最终确定」，而负权边会在后面把已确定的点改小（第 6 章 6.6 已给过反例）。所以必须换成 SPFA——允许一个点反复入队、反复变优。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector<Edge> e[N];
int dis[N];
bool inq[N]; // 是否在队列中
int main() {
int n, m, s; scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
e[u].push_back({v, w});
}
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
queue<int> q;
q.push(s); inq[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false; // 出队后清标记，允许再次入队
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
if (!inq[v]) { // 已在队里就不重复塞
q.push(v);
inq[v] = true;
}
}
}
}
for (int i = 1; i <= n; i++)
printf("%d ", dis[i] == INF ? 1000000000 : dis[i]);
return 0;
}inq 和 vis 是两回事：vis（Dijkstra 里用）表示「已永久确定」，一旦为真不再改；inq 只表示「此刻在队列里」，出队就清掉，允许下次再进。把两者混用是 SPFA 写错的第一大原因。inq[u] = false 必须在出队后立刻写。如果漏了，一个点出队后永远不会再入队，算法就退化成「只走一遍 BFS」，负权边带来的二次优化全部丢失。if (!inq[v]) 防止队列膨胀：一个点可能被多个邻居同时松弛，若每次都 push，队列里会出现大量重复。加上判断后，同一时刻每个点最多在队列里出现一次。dis[v] 真的变小了才继续——这就是「松弛」的本质。Bellman-Ford 是盲扫所有边，SPFA 只扫「刚变短的点」的出边，所以平均快得多。给定有向图，判断图中是否存在负环（环上权值之和为负）。要求检测整张图的负环，不限定从某个点可达。
输入：
4 4
1 2 1
2 3 -2
3 4 1
4 2 -1
输出：
YES
说明：2→3→4→2 权值和 = (−2)+1+(−1) = −2 < 0思路：SPFA 时维护 cnt[v] 表示「当前最短路用了几条边」，每次松弛成功就 cnt[v] = cnt[u] + 1。一旦 cnt[v] >= n，说明这条最短路用了 n 条边——n 个点不可能有 n 条边的简单路径，必然绕了负环。
关键细节：要检测「整张图」，必须把所有点的 dis 置 0 并全部入队。这样相当于加了一个超级源点，任何连通块里的负环都会被触发。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
struct Edge { int to, w; };
vector<Edge> e[N];
int dis[N], cnt[N];
bool inq[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
e[u].push_back({v, w});
}
queue<int> q;
for (int i = 1; i <= n; i++) { // 所有点都入队！
dis[i] = 0; // 距离都设 0
q.push(i);
inq[i] = true;
}
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false;
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1; // 路径边数 +1
if (cnt[v] >= n) { puts("YES"); return 0; }
if (!inq[v]) { q.push(v); inq[v] = true; }
}
}
}
puts("NO");
return 0;
}cnt[v] = cnt[u] + 1 放在「松弛成功」内部，不能放在入队处。因为 cnt 记的是路径边数，只有真的沿着这条边延伸了才 +1；若放在入队处会重复计数。cnt[v] >= n 就判定负环并直接输出。为什么是 n 而不是 n−1？n 个点的简单路径最多 n−1 条边，达到 n 条必然有重复点 = 有环，且环权和为负。return 0 立刻结束，不需要把队列跑空。判环类题目都是「发现即退出」，能省大量时间。cnt 的最大值去比较，直接看有没有触发过判定就行。cnt[v] = cnt[u]+1; if(cnt[v] >= n) 有负环，稳定可靠。n 个城市、m 条双向道路，每条有通行费。你有 k 次「免单」机会，可以让某条路的费用变 0（每条路最多用一次机会）。求从 1 到 n 的最小总花费。
输入：
4 4 1
1 2 5
2 4 5
1 3 1
3 4 10
输出：
1
说明：走 1→3→4，把 3-4 的 10 免掉，只付 1为什么普通最短路不行：同一个城市，「用掉 0 次机会」和「用掉 1 次机会」是两个不同的状态，到达它们的代价不同。一维的 dis[u] 表达不了这种区别，必须扩成二维 dis[u][j]。
建模：把图想成 k+1 层，第 j 层表示「已用 j 次机会」。同一层内正常走（付钱）；从第 j 层到第 j+1 层有一条权值为 0 的边（用掉一次机会）。然后在 2n 个「点」上跑 Dijkstra。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005, K = 12, INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector<Edge> e[N];
struct Node { // 堆元素：距离 + 点 + 已用次数
int d, u, j;
bool operator<(const Node& o) const { return d > o.d; } // 反向 = 小根堆
};
int dis[N][K];
int main() {
int n, m, k; scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
e[u].push_back({v, w});
e[v].push_back({u, w});
}
memset(dis, 0x3f, sizeof dis);
dis[1][0] = 0;
priority_queue<Node> q;
q.push({0, 1, 0});
while (!q.empty()) {
Node cur = q.top(); q.pop();
int u = cur.u, j = cur.j;
if (cur.d > dis[u][j]) continue; // 懒惰删除
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i].to, w = e[u][i].w;
// 转移 1：正常付费走
if (dis[u][j] + w < dis[v][j]) {
dis[v][j] = dis[u][j] + w;
q.push({dis[v][j], v, j});
}
// 转移 2：用掉一次机会，跳到上一层
if (j < k && dis[u][j] < dis[v][j + 1]) {
dis[v][j + 1] = dis[u][j];
q.push({dis[v][j + 1], v, j + 1});
}
}
}
int ans = INF;
for (int j = 0; j <= k; j++) ans = min(ans, dis[n][j]);
printf("%d\n", ans);
return 0;
}operator<：return d > o.d; 看着像「大根堆」，其实因为 STL 堆默认用 less（即 a < b 为真时 b 优先），把比较反过来就得到小根堆。这是最反直觉、也最容易记错的一处。dis[N][K] 是二维状态：第一维点编号、第二维「已用次数」。K 只需开到 k+1（k ≤ 10，开 12 留余量）。数组第二维一定要按题目给的 k 上限来开，开小了就是越界。dis[1][0] = 0：起点、还没用任何机会，花费 0。注意不能写成 dis[1][j] = 0 对每个 j 都置 0——那等于「免费次数凭空出现」，答案会偏小。cur.d > dis[u][j] 是二维版的懒惰删除，两个下标都要带上。写成 dis[u] 编译不过，写成 dis[u][0] 逻辑就错了。dis[v][j]，j 不变。这就是普通的沿边松弛。dis[v][j+1] = dis[u][j]，注意右边不加 w，因为这条免费。同时要判 j < k，否则会越界写坏内存。min(dis[n][0..k])，不是 dis[n][k]。因为机会不一定都要用掉——可能用 0 次就已经最优（比如开始就在终点），也可能用 1 次比用满 k 次更好。dis[u][1<<m]）。| 算法 | 复杂度 | 核心 / 用途 |
|---|---|---|
| Bellman-Ford | O(nm) | n−1 轮全边松弛；多做一轮可判负环。允许负权，实现最简。 |
| SPFA | 平均 O(km)，最坏 O(nm) | 队列版 BF，只扩散「刚变短」的点；cnt[v] ≥ n 判负环。 |
| 分层图 | O(k·m log(km)) | 给状态加一维，用 Dijkstra 解「有次数限制」的最短路。 |
前两章问「怎么走最快」，这一章换一个问题：要让所有点都连通，最少要花多少钱？。答案就是最小生成树。它是「修路 / 铺管道 / 架电网 / 组网」类问题的标准解法，也是并查集最经典的应用场景。
先明确三个概念：
Kruskal 的核心动作是：「这条边的两个端点，是不是已经在同一块里了？」是 → 加了会成环，跳过；否 → 加进去并把两块合并。这个「判断连通 + 合并」正是并查集的看家本领。
int fa[N];
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i; // 初始每人自成一个集合
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]); // 路径压缩：顺手把路上的点都挂到根上
}
// 合并 a、b 所在集合；若本来就在一起，返回 false
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
fa[a] = b; // 把 a 的根挂到 b 的根下
return true;
}
// 判断是否连通：find(a) == find(b)fa[x] = find(fa[x]) 里的赋值是关键。如果只写 return find(fa[x])，树会退化成一条长链，单次查询 O(n)，Kruskal 直接 TLE。加上压缩后，均摊复杂度近似 O(α(n)) ≈ O(1)。Kruskal 的思路短到一句话就能说完：
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 200005;
struct Edge { int u, v; long long w; } E[M];
int fa[N];
bool cmp(const Edge& a, const Edge& b) { return a.w < b.w; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%lld", &E[i].u, &E[i].v, &E[i].w);
sort(E + 1, E + m + 1, cmp); // 第 1 步：按边权升序
for (int i = 1; i <= n; i++) fa[i] = i; // 并查集初始化
long long sum = 0;
int cnt = 0; // 已选边数
for (int i = 1; i <= m; i++) { // 第 2 步：依次尝试
int a = find(E[i].u), b = find(E[i].v);
if (a == b) continue; // 已成环，跳过
fa[a] = b; // 选它！合并两块
sum += E[i].w;
cnt++;
if (cnt == n - 1) break; // 第 3 步：够了就停
}
if (cnt < n - 1) puts("orz"); // 图不连通
else printf("%lld\n", sum);
return 0;
}fa[N] 是并查集的父指针数组。fa[i] = i 表示 i 自成一个集合；find 一路向上找到根，根相同的两个点就在同一连通块。cmp 决定排序方向：a.w < b.w 是升序（最小生成树），改成 > 就是最大生成树。整个算法只有这一处方向，其余代码完全对称。fa[x] = find(fa[x]) 的赋值是整个表达式的一部分——它在递归返回时把路上的点都直接挂到根上。只写 return find(fa[x]) 不算错，但树会退化成链，单次查询 O(n)，大数据必 TLE。sort(E+1, E+m+1, cmp) 左闭右开：下标 1 到 m 参与排序，所以右端写 m+1。写成 E+m 会漏掉最后一条边。find 认为所有点同根，第一条边就判成环，一条都选不上。a == b 表示两端已连通，加这条边会成环，跳过。自环（u==v）在这里天然被判掉；重边中较大的那条也会因为「已连通」被跳掉，所以两者都不用特判。fa[a] = b 是「把 a 的根挂到 b 的根下」，注意合并的是根不是原结点；sum += E[i].w 用 long long；cnt++ 用于判断是否够 n−1 条。cnt < n-1 判不连通。n 个点至少要 n−1 条边才能连成一体，不够说明有孤立块。不判这一点，不连通的数据会输出一个偏小的"正常"答案，是最隐蔽的 WA。复杂度：排序 O(m log m) 是瓶颈，并查集近似 O(1)，总 O(m log m)。适合稀疏图（m 不太大），也是实际比赛中最常用的写法——因为代码短、不容易写错。
边与权值：1-2(6)、1-3(1)、1-4(5)、2-3(5)、2-5(3)、3-4(5)、3-5(6)、3-6(4)、4-6(2)、5-6(6)。
用 Prim 从 1 号点出发验证：依次选入 3(1)、6(4)、4(2)、2(5)、5(3)，合计 1+4+2+5+3 = 15，两种算法结果一致。
Prim 换了视角：维护一个「已加入树的点集」，每轮从连接树内与树外的边里选权值最小的那条，把对应点拉进来。n−1 轮后树就长满了。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dis[N]; // 注意！Prim 的 dis[v] = v 到「已选点集」的最小边权
bool vis[N]; // 不是「到起点的距离」，别和 Dijkstra 混！
int prim() {
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
dis[1] = 0;
long long sum = 0;
for (int i = 1; i <= n; i++) {
int u = -1;
for (int j = 1; j <= n; j++)
if (!vis[j] && (u == -1 || dis[j] < dis[u])) u = j;
if (dis[u] == INF) return -1; // 图不连通
vis[u] = true;
sum += dis[u]; // 把这条入树边计入答案
for (int v = 1; v <= n; v++)
if (!vis[v] && g[u][v] < dis[v]) dis[v] = g[u][v];
// 关键区别：这里不是 dis[u] + g[u][v]，而是直接取边权！
}
return (int)sum;
}dis[v] = dis[u] + g[u][v]，累加的是「到起点的整条路径」。dis[v] = g[u][v]，只取「这一条入树边」的权值。复杂度：外层 n 轮，内层找最小 O(n) + 更新 O(n)，共 O(n²)，与边数无关 → 稠密图（m ≈ n²）首选。用堆优化可到 O(m log m)，但常数比 Kruskal 大，实战中稀疏图大家更爱 Kruskal。
| 对比项 | Kruskal | Prim |
|---|---|---|
| 核心思想 | 按边权从小到大加边，用并查集防环 | 从一个点出发，每次拉最近的点入树 |
| 复杂度 | O(m log m) | 朴素 O(n²)；堆优化 O(m log m) |
| 适合图型 | 稀疏图（m ≈ n ~ n log n） | 稠密图（m ≈ n²） |
| 是否需要邻接结构 | 不需要，边表就够 | 朴素版用邻接矩阵最方便 |
| 代码难度 | 很短，但要会并查集 | 很像 Dijkstra，容易与最短路混淆 |
| 处理不连通 | 天然支持，最后判 cnt < n−1 | 需要额外判 dis == INF |
| 推荐场景 | 比赛默认选择（尤其 m ≤ 2×10⁵） | n ≤ 5000 且边很密时更快 |
orz。直接套 8.3 的模板即可。几个必须处理的细节：
find(u) == find(v) 恒成立，自动跳过，也不用特判。cnt < n-1，说明有孤立块 → 输出 orz。输入：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出：
7
选边：1-2(2) → 1-3(2) → 1-4(3)，合计 2+2+3 = 7注意 3-4 也是 3，选它同样得 7 —— 说明边权有相等值时 MST 可能不唯一，但总权一定相同。题目只问总权，所以不影响答案。
关键技巧：把已修好的路的代价设为 0。因为「已经连通」意味着这几条边可以免费使用。把这些边权改成 0 一起丢进 Kruskal，算法会自动优先选它们（0 是最小的），相当于先把已有的连通块合并好，再花钱补缺口。
int main() {
int n, k, m;
scanf("%d%d", &n, &k); // k 条已修好的路
for (int i = 1; i <= n; i++) fa[i] = i;
int tot = 0;
for (int i = 1; i <= k; i++) {
int u, v; scanf("%d%d", &u, &v);
E[++tot] = {u, v, 0}; // 关键：代价记 0
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int u, v; long long w;
scanf("%d%d%lld", &u, &v, &w);
E[++tot] = {u, v, w};
}
sort(E + 1, E + tot + 1, cmp);
long long sum = 0; int cnt = 0;
for (int i = 1; i <= tot; i++) {
int a = find(E[i].u), b = find(E[i].v);
if (a == b) continue;
fa[a] = b; sum += E[i].w; cnt++;
if (cnt == n - 1) break;
}
if (cnt < n - 1) puts("无法连通");
else printf("%lld\n", sum);
return 0;
}MST 的代码短，但细节多：排序方向、并查集初始化、连通性判断、long long。下面 3 道题把「标准最小」「已有边」「最大生成树」都走一遍。
n 个点、m 条无向边（可能有重边、自环、负权）。求最小生成树的边权之和；若图不连通，输出 orz。
输入：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出：
7
选边：1-2(2)、1-3(2)、1-4(3)，合计 7思路：Kruskal——边按权升序排序，依次尝试，用并查集判断两端是否已连通。选够 n−1 条即停；循环结束还没选够就是图不连通。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 200005;
struct Edge { int u, v; long long w; } E[M];
int fa[N];
bool cmp(const Edge& a, const Edge& b) { return a.w < b.w; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%lld", &E[i].u, &E[i].v, &E[i].w);
sort(E + 1, E + m + 1, cmp); // ① 按边权升序
for (int i = 1; i <= n; i++) fa[i] = i; // ② 并查集初始化
long long sum = 0;
int cnt = 0;
for (int i = 1; i <= m; i++) {
int a = find(E[i].u), b = find(E[i].v);
if (a == b) continue; // ③ 已成环，跳过
fa[a] = b; // ④ 合并
sum += E[i].w;
cnt++;
if (cnt == n - 1) break; // ⑤ 够了就停
}
if (cnt < n - 1) puts("orz");
else printf("%lld\n", sum);
return 0;
}cmp 必须写成 a.w < b.w（升序）。写成大于号就变成最大生成树了——这是 P8-3 才会用到。排序方向错了，答案会完全反过来。fa[x] == x ? x : fa[x] = find(fa[x])。赋值 fa[x] = ... 是必须的，它把路径上的点直接挂到根，省掉后续查询的遍历。只写 return find(fa[x]) 会退化成链。sort(E+1, E+m+1, cmp) 左闭右开：从下标 1 排到下标 m（含），所以右端点是 m+1。写成 E+m 会漏掉最后一条边，某些数据下答案偏大。fa[i] = i 表示每个点自成一个集合。漏了这一句，fa 全是 0，find 会把所有点当成同一个集合，一条边都选不上。a == b 说明两端已在同一连通块，加这条边会形成环，直接跳过。自环（u == v）在这里天然被跳过，不用特判；重边中较大的那条也会因为「已成环」被跳掉。cnt++ 就永远不会 break，会把所有能选的边都选完（但因为成环判断，结果恰好还是 n−1 条——只是白跑）；漏了 sum += 则答案恒为 0。cnt < n-1 判不连通：n 个点至少要 n−1 条边才能连通。少于这个数说明有的点根本没边可连。这一步不能省，否则不连通时会输出一个「看起来正常」的偏小答案。n 个村庄，其中 k 条路已经修好（可以免费通行）。另有 m 条路允许修，各有造价。求让所有村庄连通的最小总造价。
输入：
5 2
1 2
3 4
3
1 3 5
2 3 6
4 5 2
输出：
7
说明：已通 1-2、3-4 免费；再修 4-5(2) 和 1-3(5)，总花费 2+5 = 7关键技巧：把已修好的路的造价设为 0。因为「已经能走」等价于「这条边的代价是 0」。把它们和普通边一起丢进 Kruskal，算法会优先选它们（0 是最小的），相当于先把已有的连通块合并好，再花钱补缺口。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 400005;
struct Edge { int u, v; long long w; } E[M];
int fa[N], tot;
bool cmp(const Edge& a, const Edge& b) { return a.w < b.w; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
int n, k; scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= k; i++) {
int u, v; scanf("%d%d", &u, &v);
E[++tot] = {u, v, 0}; // 已修好：代价 0
}
int m; scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int u, v; long long w;
scanf("%d%d%lld", &u, &v, &w);
E[++tot] = {u, v, w};
}
sort(E + 1, E + tot + 1, cmp);
long long sum = 0;
int cnt = 0;
for (int i = 1; i <= tot; i++) {
int a = find(E[i].u), b = find(E[i].v);
if (a == b) continue;
fa[a] = b;
sum += E[i].w;
if (++cnt == n - 1) break;
}
if (cnt < n - 1) puts("无法连通");
else printf("%lld\n", sum);
return 0;
}tot 而不是 m 当边数。因为边表里混合了「已有边」和「可修边」两类，总数是 k+m。把两种来源合并到一个数组里统一排序，是这类题最省事的写法。E[++tot] = {u, v, 0}：C++11 的花括号初始化，等价于逐个赋值。写成 E[tot] = ... 而不先 ++tot 会覆盖上一条边。sum 会变成负数，最后还要加回来——多余且易错。0 是语义最干净的选择。long long w 读入，再存进结构体。若这里用 int 读 10⁹ 再加上 sum，累加过程会溢出。sort(E+1, E+tot+1, cmp) 排的是全部 k+m 条边，权重 0 的已有边自然跑到最前面，先被处理。if (++cnt == n-1) break; 把「自增」和「判断」写在一句里。因为 cnt 只在这里用，合并更紧凑；注意必须是前自增 ++cnt，cnt++ 会先比较后加导致差一。0；② 必须选的边 → 权值设 -INF，或用并查集预先合并；③ 禁用的边 → 干脆不加进边表。求边权之和最大的生成树（仍要求 n−1 条边、连通、无环）。若图不连通输出 -1。
输入：
4 4
1 2 5
2 3 4
3 4 3
1 4 10
输出：
19
选边：1-4(10)、1-2(5)、2-3(4)，合计 19改动只有一处：把比较函数从 a.w < b.w 改成 a.w > b.w，让边从大到小排序。Kruskal 的贪心逻辑完全对称——「每次选当前能选的最大边」得到的就是最大生成树。
另一种等价写法：把所有边权取负，跑最小生成树，最后答案取负。两种都对，但直接改排序更直观。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 200005;
struct Edge { int u, v; long long w; } E[M];
int fa[N];
bool cmp(const Edge& a, const Edge& b) { return a.w > b.w; } // 降序！
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%lld", &E[i].u, &E[i].v, &E[i].w);
sort(E + 1, E + m + 1, cmp);
for (int i = 1; i <= n; i++) fa[i] = i;
long long sum = 0;
int cnt = 0;
for (int i = 1; i <= m; i++) {
int a = find(E[i].u), b = find(E[i].v);
if (a == b) continue;
fa[a] = b; sum += E[i].w; cnt++;
if (cnt == n - 1) break;
}
printf("%lld\n", cnt == n - 1 ? sum : -1);
return 0;
}a.w > b.w 就是全部区别。C++ 的 sort 按「比较函数返回真」的顺序排列，所以返回 a.w > b.w 时大的排前面。把这一行和 P8-1 对比着记，两个模板就都掌握了。| 要点 | 内容 |
|---|---|
| MST 定义 | n 个点、n−1 条边、连通无环、总权最小 |
| Kruskal | 边排序 → 并查集判环 → 选够 n−1 条。O(m log m)，稀疏图首选 |
| Prim | 点集扩张，每次取最小跨界边。O(n²)，稠密图首选 |
| 最易错 | Prim 的 dis[v] = g[u][v] 不是 dis[u]+g[u][v] |
| 三大变形 | 已有边权置 0、必选边权置 −INF、禁用边不入表 |
| 理论武器 | 割性质（最小跨界边必在 MST）、环性质（最大环边必不在 MST） |
这一章是给学有余力的同学准备的「上限拓展」。CSP-J 不会考，但 CSP-S / NOIP 里它们是常客，而且思路都非常漂亮——一次 DFS 就能算出整张图的结构信息。看不懂可以先跳过，等打完 CSP-J 再回来。
在有向图里，「连通」要分强弱：
Tarjan 算法只用一次 DFS。它给每个点记两个值：
dfn[u]：时间戳，第几个被访问到。low[u]：从 u 出发、只经过 DFS 栈里的点，能回溯到的最小 dfn。当 low[u] == dfn[u] 时，说明 u 是这个 SCC 里「最靠上」的点，此时把栈里从 u 到栈顶的所有点弹出，它们就构成一个 SCC。
int dfn[N], low[N], timer;
int stk[N], top, scc[N], sccCnt;
bool inStk[N];
void tarjan(int u) {
dfn[u] = low[u] = ++timer; // 打时间戳
stk[++top] = u; inStk[u] = true; // 入栈
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = to[i];
if (!dfn[v]) { // 树边：先递归
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inStk[v]) { // 后向边 / 横叉边：只在栈内才有意义
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) { // u 是本 SCC 的根
sccCnt++;
while (true) {
int v = stk[top--];
inStk[v] = false;
scc[v] = sccCnt; // 标记所属 SCC
if (v == u) break;
}
}
}
// 主函数里对所有未访问点调用 tarjan(i)，注意图可能不连通else if (inStk[v]) low[u] = min(low[u], dfn[v]) —— 用 dfn 不是 low[v]；// 1. 先跑一遍 tarjan，得到 scc[u]（每个点属于哪个分量）
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
// 2. 把点权累加到分量上
for (int i = 1; i <= n; i++) w[scc[i]] += a[i];
// 3. 遍历所有边，若两端不属于同一分量，就加一条新边
for (int u = 1; u <= n; u++)
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = to[i];
if (scc[u] != scc[v]) add2(scc[u], scc[v]);
}
// 4. 新图一定是 DAG，可以直接拓扑排序 + DP在无向连通图里：
它们描述的是「网络的瓶颈」：一个通信网里，割点就是「一旦瘫痪就全网分区」的关键节点。
int dfn[N], low[N], timer;
bool cut[N]; // cut[u] = true 表示 u 是割点
void dfs(int u, int fa) {
dfn[u] = low[u] = ++timer;
int child = 0; // u 在 DFS 树里的孩子数
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = to[i];
if (v == fa) continue; // 无向图不能走回父亲（有重边时要改成判边编号）
if (!dfn[v]) {
child++;
dfs(v, u);
low[u] = min(low[u], low[v]);
// 非根节点：只要有一个孩子回不到 u 的祖先，u 就是割点
if (fa != 0 && low[v] >= dfn[u]) cut[u] = true;
} else {
low[u] = min(low[u], dfn[v]);
}
}
// 根节点单独判：有两棵以上子树才是割点
if (fa == 0 && child >= 2) cut[u] = true;
}
// 主函数：对每个未访问点调用 dfs(i, 0)low[v] >= dfn[u]（v 顶多回到 u 自己，删掉 u 就上不去了）low[v] > dfn[u]（v 连 u 都回不到，删掉这条边必然断开）if (v == fa) continue; 跳过父亲，在有重边时会出错：u 和 v 之间有两条边，走第一条到 v 后，第二条本应让 v 的 low 变小，但被这句直接跳过了，导致误判成桥。if (i == (from ^ 1)) continue;（链式前向星建边时成对编号，^1 就是反向边）。匹配：在二分图里选若干条边，要求任意两条边不共用端点。边的数量最多能达到多少，就是最大匹配。
典型场景：n 个学生、m 个任务，每个学生只能做自己能做的任务，每个任务只能派给一个人，最多能安排多少个任务？
#include <bits/stdc++.h>
using namespace std;
vector<int> g[N]; // g[u]：左部点 u 可连的右部点
int match[N]; // match[v]：右部点 v 目前配给了哪个左部点（0 = 未匹配）
bool vis[N]; // vis[v]：本轮 DFS 中右部点 v 是否已被尝试过
bool dfs(int u) {
for (int i = 0; i <(int)g[u].size(); i++) {
int v = g[u][i];
if (vis[v]) continue; // 本轮已经试过，别再绕回来（防死循环）
vis[v] = true;
// v 没被占，或占它的人能换到别处 → 让出来
if (match[v] == 0 || dfs(match[v])) {
match[v] = u;
return true;
}
}
return false;
}
int main() {
int n, m, e; scanf("%d%d%d", &n, &m, &e);
for (int i = 1; i <= e; i++) {
int u, v; scanf("%d%d", &u, &v);
g[u].push_back(v);
}
int ans = 0;
for (int u = 1; u <= n; u++) {
memset(vis, 0, sizeof vis); // 每个左部点重新清空！
if (dfs(u)) ans++;
}
printf("%d\n", ans);
return 0;
}vis 必须在每个左部点开始前清空，且在 dfs 内部只对右部点标记——它表示「这一轮增广里，这个右部点已经被考虑过了」，避免无限递归；两个常与前面算法搭配出现的小技巧，各给一句核心。
求「从 s 到 t 有多少条最短路」。在松弛时多维护一个 cnt[]：
· 若 dis[u]+w < dis[v]：dis[v]=dis[u]+w; cnt[v]=cnt[u];
· 若 dis[u]+w == dis[v]：cnt[v]=(cnt[v]+cnt[u])%MOD;
用 Dijkstra 时必须按 dis 从小到大传播，否则计数会被重复累加。所以别用 SPFA 做计数。
先求出一棵 MST，然后枚举每一条非树边 (u,v,w)：把它加进树会形成一个环，环上权值最大的那条树边 f 可以被替换掉，新树权 = MST总权 + w − w(f)。
取所有替换方案中最小且严格大于 MST 的那个，就是次小生成树。环上最大边用树上倍增（LCA）或暴力求均可。
这两题是 CSP-S 难度的入门，CSP-J 不会考。但如果你已经能独立写出前 8 章的题，这两道正好用来检验「能不能读懂别人的算法框架并改写成自己的代码」。
有 n 个点，第 i 个点有权值 a[i]（可能为负）。m 条有向边，允许重复经过同一个点，但同一个点的权值只算一次。求从 1 号点出发，能获得的最大权值和。
输入：
4 4
1 2 3 4
1 2
2 1
2 3
3 4
输出：
10
说明：1 与 2 互相可达（一个 SCC），能全吃掉 = 1+2 = 3；
再走 3(3) → 4(4)，总计 3+3+4 = 10思路（三步走）：
f[v] = max(f[v], f[u] + sw[v])，只从 1 号分量出发传播。#include <bits/stdc++.h>
using namespace std;
const int N = 10005, INF = 0x3f3f3f3f;
vector<int> e[N], g[N]; // e 原图，g 缩点后的 DAG
int dfn[N], low[N], timer;
int stk[N], top, scc[N], sccCnt;
bool inStk[N];
int a[N], sw[N], indeg[N], f[N];
void tarjan(int u) {
dfn[u] = low[u] = ++timer;
stk[++top] = u; inStk[u] = true;
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i];
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inStk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
sccCnt++;
while (true) {
int v = stk[top--];
inStk[v] = false;
scc[v] = sccCnt;
if (v == u) break;
}
}
}
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); // ① 缩点
for (int i = 1; i <= n; i++) sw[scc[i]] += a[i]; // ② 合并点权
for (int u = 1; u <= n; u++)
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i];
if (scc[u] != scc[v]) {
g[scc[u]].push_back(scc[v]); // ③ 建新图
indeg[scc[v]]++;
}
}
memset(f, 0xc0, sizeof f); // -INF
f[scc[1]] = sw[scc[1]];
queue<int> q;
for (int c = 1; c <= sccCnt; c++) if (indeg[c] == 0) q.push(c);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)g[u].size(); i++) {
int v = g[u][i];
if (f[u] != -INF) f[v] = max(f[v], f[u] + sw[v]); // ④ DP
if (--indeg[v] == 0) q.push(v);
}
}
int ans = -INF;
for (int c = 1; c <= sccCnt; c++) ans = max(ans, f[c]);
printf("%d\n", ans);
return 0;
}!dfn[v] 是树边（继续递归，用 low[v] 更新）；inStk[v] 是回边（用 dfn[v] 更新）。回边只能用 dfn，用 low[v] 会算错。low[u] == dfn[u] 说明 u 是分量的根，此时栈里从 top 到 u 的所有点构成一个 SCC。这个判断必须放在递归返回之后，不能提前。stk[top--]、再清 inStk、再赋 scc，最后判断是否等于 u。如果先判断再弹，u 自己会漏掉。这是最典型的「顺序写错就少一个点」。tarjan(1) 会漏掉其他块，那些点的 scc 还是 0，后面全部出错。sw[scc[i]] += a[i]。同一个 SCC 内的点互相可达，所以它们的权值可以全部吃到——这就是「缩点」在这类题里的物理意义。scc[u] != scc[v] 时加新边。同分量内部的边全部丢弃（它们已经"内化"成点权了）。注意这里可能会产生重边，但拓扑排序与 DP 都不受影响，不用去重。memset(f, 0xc0, sizeof f) 是置 −INF 的常用写法（0xc0c0c0c0 ≈ −1.06×10⁹）。不能用 0x3f（那是正无穷），也不能用 −1（权值可能真的是 −1）。f[scc[1]]，其余保持 −INF。这样 DP 时只有从 1 号分量出发的路径才会被传播，从别的分量起步的路径不会污染答案。if (f[u] != -INF) 判断是否可达。不可达的分量 f 是 −INF，若直接加 sw[v] 会溢出成更小的负数，甚至变成正数。这一句是负权 DP 的安全阀。f[scc[n]]。因为最优路径可能停在任何一个分量上。若题目要求「必须到 n 号点」，才改成输出 f[scc[n]]。给定无向图（可能不连通），求割点的个数。割点指：删掉这个点（及与之相连的所有边）后，图的连通块数量会增加的顶点。
输入：
4 3
1 2
2 3
3 4
输出：
2
说明：这是一条链 1-2-3-4。删掉 2 → {1} 与 {3,4} 分离；删掉 3 同理。
1 和 4 是端点，删掉它们只会少一个点，不算割点思路：Tarjan 求 dfn/low。对非根节点 u，若存在孩子 v 满足 low[v] >= dfn[u]，则 u 是割点（v 及其子树回不到 u 的祖先，只能"卡"在 u 这里）。根节点单独判：孩子数 ≥ 2 才是割点。
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
vector<int> e[N];
int dfn[N], low[N], timer;
bool cut[N];
void dfs(int u, int fa) {
dfn[u] = low[u] = ++timer;
int child = 0; // DFS 树上的孩子数
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i];
if (v == fa) continue; // 不走回父亲
if (!dfn[v]) {
child++;
dfs(v, u);
low[u] = min(low[u], low[v]);
if (fa != 0 && low[v] >= dfn[u]) cut[u] = true;
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (fa == 0 && child >= 2) cut[u] = true; // 根的特殊判定
}
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) dfs(i, 0); // 0 表示没有父亲
int ans = 0;
for (int i = 1; i <= n; i++) if (cut[i]) ans++;
printf("%d\n", ans);
return 0;
}fa 用 0 表示「没有父亲」，因为点编号从 1 开始，0 一定不是合法点。这样就能用 fa == 0 判断当前是否是 DFS 树的根。child 只统计 DFS 树上的孩子（即 !dfn[v] 的那条分支），不包括「已访问的祖先或兄弟」。这个数只用于根节点的判定。if (v == fa) continue; 跳过父节点，否则会在父子之间来回递归、死循环。但这一句在有重边时会出错（见下方警示）。low[v] >= dfn[u] 是割点的判据：v 最多只能回到 u 自己，回不到 u 的祖先。所以删掉 u 之后，v 那棵子树就与外界失联了。注意是 大于等于。fa != 0 限定「非根」：根节点不适用这个判据，因为根没有祖先，low[v] >= dfn[root] 几乎永远成立。根要用 child >= 2 单独判。dfn[v] 更新 low，不是 low[v]。这与 Tarjan 求 SCC 完全一致——都是「回边取 dfn」。child 才是最终值。放在循环里判断会因为计数不全而误判。fa = 0 调用。low[v] 变小；但 if (v == fa) continue; 会把它当成「回到父亲」直接跳过，导致误判成割点/桥。if (i == (from ^ 1)) continue;，其中 from 是走到 u 时用的那条边的编号。low[v] >= dfn[u]；桥：low[v] > dfn[u]。>= 改成 >，并把标记从点换成「这条边的编号」，就得到求桥的代码。两道题可以一起背。| 内容 | 核心判据 / 复杂度 |
|---|---|
| Tarjan 求 SCC | low[u]==dfn[u] 则弹栈成组；O(n+m) |
| 缩点 | 同一 SCC 压成一点，得 DAG，可拓扑 + DP |
| 割点 | 非根：low[v] >= dfn[u]；根：子树 ≥ 2 |
| 桥 | low[v] > dfn[u]（注意重边要用边编号跳过） |
| 匈牙利匹配 | DFS 找增广路，「请对方让位」；O(nm) |
| 最短路计数 | 松弛时同步维护 cnt，只在严格更短/相等时分别处理 |
| 次小生成树 | 枚举非树边，替换环上最大树边 |
13 道编程题，分三档。先自己做，做完再点开折叠的参考答案对照——13 份代码全部用 g++ 编译、用样例与边界数据实测通过，可直接照抄提交。答案前面那句「点睛」讲的是这道题最容易踩的坑，建议先看它再读代码。
这一组的目的是「把模板写熟」。如果某题卡住了，说明对应章节的模板还没背下来，回去重抄三遍。
给出 n 个点的度数序列，判断它能否构成一个无向图（不要求简单图）。只需用到握手定理。
第一行 n，第二行 n 个整数表示各点度数。
能构成输出 YES，否则 NO。
long long，n 到 10⁵、度数可能很大。puts(sum % 2 == 0 ? "YES" : "NO");握手定理的逆命题不成立——度数全为偶数并不保证能构成简单图；但本题明确写了「不要求简单图」，所以只判奇偶就是完整答案。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; scanf("%d", &n);
long long sum = 0; // n 到 1e5，度数可能很大，求和一律 long long
for (int i = 1; i <= n; i++) {
long long d; scanf("%lld", &d);
sum += d;
}
puts(sum % 2 == 0 ? "YES" : "NO"); // 握手定理：Σ度 = 2m 必为偶数
return 0;
}O(n) 时间、O(1) 额外空间。注意用 long long 求和，不必真的建图。
对每个点输出 出度 入度，并额外输出一行「入度为 0 的点数」与「出度为 0 的点数」。
outdeg[]、indeg[]，读边时 outdeg[u]++、indeg[v]++。关键认识：统计度数根本不需要邻接结构。边读进来就地加一，省下建图的整段代码，也省下 O(n+m) 的内存。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int indeg[N], outdeg[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
outdeg[u]++; // u 出去一条
indeg[v]++; // v 进来一条
}
int zi = 0, zo = 0;
for (int i = 1; i <= n; i++) {
printf("%d %d\n", outdeg[i], indeg[i]);
if (indeg[i] == 0) zi++;
if (outdeg[i] == 0) zo++;
}
printf("%d %d\n", zi, zo);
return 0;
}O(n+m) 时间、O(n+m) 空间（两个计数数组）。自环给入度、出度各 +1，无需特判。
读入一个用边表描述的有向图，输出它的邻接矩阵。
bool g[1005][1005]（约 1MB），读边时 g[u][v] = true。printf("%d ", (int)g[i][j])，bool 直接打印是 1/0，但加强制转换更保险。矩阵版的有效代码只有 6 行。真正要记住的是容量上限：1000² 个 bool ≈ 1MB 很安全，100000² 就是 10GB，直接崩。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
bool g[N][N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
g[u][v] = true; // 有向图只标一个方向
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
printf("%d%c", (int)g[i][j], j == n ? '\n' : ' ');
}
return 0;
}O(n²) 时间与空间。n ≤ 1000 是邻接矩阵的实用边界。
求连通块个数，以及最大的那个连通块包含几个点。
mx = max(mx, cnt)，不用存数组。「入队即标记」在这里千万不能省：若等出队才标记，同一个点会被多个邻居重复塞进队列，队列长度爆炸、内存超限。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> e[N];
bool vis[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v); e[v].push_back(u); // 无向边两头都要加
}
int blocks = 0, mx = 0;
for (int s = 1; s <= n; s++) {
if (vis[s]) continue;
blocks++;
int cnt = 0;
queue<int> q; q.push(s); vis[s] = true; // 入队即标记
while (!q.empty()) {
int u = q.front(); q.pop(); cnt++;
for (int v : e[u])
if (!vis[v]) { vis[v] = true; q.push(v); }
}
mx = max(mx, cnt);
}
printf("%d %d\n", blocks, mx);
return 0;
}O(n+m)。每个点最多进队一次，每条边被看两次（无向图两头各一次）。
n 门课，m 条先修关系 u v（学 v 前必须学 u）。判断能否修完全部课程。
tot == n。判环的正确姿势是数点数：只有「排出来的点数 = n」才等价于无环。看队列空不空、看有没有入度 0 的点，都是不充分的。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> e[N];
int indeg[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v);
indeg[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push(i);
int tot = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); tot++;
for (int v : e[u]) if (--indeg[v] == 0) q.push(v);
}
puts(tot == n ? "YES" : "NO");
return 0;
}O(n+m)。有环时环上的点入度永远减不到 0，tot 必然小于 n。
无向带权图，q 次询问 u 到 v 的最短距离，不可达输出 −1。
memset(dis, 0x3f)、dis[i][i] = 0、重边取 min。三重循环里 k 是「允许经过的中间点编号 ≤ k」，它是 DP 的阶段，所以必须在最外层；写在内层就退化成错误的贪心。
#include <bits/stdc++.h>
using namespace std;
const int N = 305, INF = 0x3f3f3f3f;
int dis[N][N];
int main() {
int n, m; scanf("%d%d", &n, &m);
memset(dis, 0x3f, sizeof(dis)); // 全部先设为不可达
for (int i = 1; i <= n; i++) dis[i][i] = 0;
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
dis[u][v] = min(dis[u][v], w); // 重边取较小值
dis[v][u] = min(dis[v][u], w); // 无向图对称
}
for (int k = 1; k <= n; k++) // k 必须在最外层
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dis[i][k] + dis[k][j] < dis[i][j])
dis[i][j] = dis[i][k] + dis[k][j];
int q; scanf("%d", &q);
while (q--) {
int u, v; scanf("%d%d", &u, &v);
printf("%d\n", dis[u][v] >= INF ? -1 : dis[u][v]);
}
return 0;
}O(n³ + q)。n=300 时约 2.7×10⁷ 次运算，稳过；预处理一次，每次询问 O(1)。
标准堆优化 Dijkstra。不可达输出 −1。
priority_queue<pair<long long,int>, vector<...>, greater<...>>。0x3f3f3f3f3f3f3f3fLL）。if (d > dis[u]) continue;，否则重复扩展会 TLE。三处 long long 缺一不可：dis 数组、堆里的 pair、INF 常量。最容易漏的是堆元素——写成 int 会在 w ≤ 10⁹、路径又长时溢出成负数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005, M = 400005;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
int head[N], nxt[M], to[M], cntE;
ll w[M], dis[N];
void add(int u, int v, ll c) {
to[++cntE] = v; w[cntE] = c;
nxt[cntE] = head[u]; head[u] = cntE;
}
int main() {
int n, m, s; scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
int u, v; ll c; scanf("%d%d%lld", &u, &v, &c);
add(u, v, c); // 无向图：反向再 add 一次
add(v, u, c);
}
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
pq.push({0, s});
while (!pq.empty()) {
pair<ll,int> pr = pq.top(); pq.pop();
ll d = pr.first; int u = pr.second;
if (d > dis[u]) continue; // 过期的旧记录，扔掉
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (d + w[i] < dis[v]) {
dis[v] = d + w[i];
pq.push({dis[v], v});
}
}
}
for (int i = 1; i <= n; i++)
printf("%lld%c", dis[i] >= INF / 2 ? -1LL : dis[i], i == n ? '\n' : ' ');
return 0;
}O(m log m)。每条边最多触发一次入堆，堆大小 O(m)。
边权可能为负，数据保证从 s 不可达负环。求 s 到各点的最短路。
inq 标记，出队即清标记。inq 与队列必须严格同步：入队置 true、出队置 false。漏掉出队清零，一个点只会被扩展一次，负权带来的二次优化全部丢失，答案偏大。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005, M = 400005;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
int head[N], nxt[M], to[M], cntE;
ll w[M], dis[N];
bool inq[N];
void add(int u, int v, ll c) {
to[++cntE] = v; w[cntE] = c;
nxt[cntE] = head[u]; head[u] = cntE;
}
int main() {
int n, m, s; scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
int u, v; ll c; scanf("%d%d%lld", &u, &v, &c);
add(u, v, c); // 有向边，只加一次
}
for (int i = 1; i <= n; i++) dis[i] = INF;
queue<int> q;
dis[s] = 0; q.push(s); inq[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false; // 出队清标记，之后还能再进来
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (dis[u] + w[i] < dis[v]) {
dis[v] = dis[u] + w[i];
if (!inq[v]) { inq[v] = true; q.push(v); }
}
}
}
for (int i = 1; i <= n; i++)
printf("%lld%c", dis[i] >= INF / 2 ? 1000000000000000000LL : dis[i], i == n ? '\n' : ' ');
return 0;
}平均 O(km)、最坏 O(nm)。随机数据 k≈2~3；本题无负环，所以循环一定终止。
求最小生成树的边权之和，不连通输出 orz。
sort(E+1, E+m+1, cmp) 注意右端点是 m+1（左闭右开）。fa[i] = i，路径压缩写成 fa[x] = find(fa[x])。cnt < n-1，否则不连通时会输出偏小答案。判不连通必须在循环结束后看 cnt，不能在循环里提前返回。否则不连通的数据会输出一个「看起来正常但偏小」的答案——这是最隐蔽的 WA。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 200005;
struct Edge { int u, v, w; } e[M];
int fa[N];
bool cmp(const Edge &a, const Edge &b) { return a.w < b.w; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
sort(e + 1, e + m + 1, cmp); // 左闭右开，右端写 m+1
for (int i = 1; i <= n; i++) fa[i] = i; // 并查集初始化
long long sum = 0; int cnt = 0;
for (int i = 1; i <= m; i++) {
int a = find(e[i].u), b = find(e[i].v);
if (a == b) continue; // 已成环，跳过
fa[a] = b;
sum += e[i].w; cnt++;
if (cnt == n - 1) break; // 够 n-1 条即停
}
if (cnt < n - 1) puts("orz"); // 不连通
else printf("%lld\n", sum);
return 0;
}O(m log m)。排序是瓶颈，并查集带路径压缩近似 O(1)。
每项工程有耗时，给出依赖关系，工程可并行。求整个项目的最短完工时间。
f[v] = max(f[v], f[u] + t[v])，必须按拓扑序。f[i] = t[i]，这是 DP 的边界。max(f[i])，不是 f[n]。把 f[i] 全部初始化为 t[i] 是一行漂亮的写法：对入度 0 的点它就是边界，对其余点会被后面的 max 自然覆盖。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10005;
vector<int> e[N];
int indeg[N], t[N];
ll f[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) { scanf("%d", &t[i]); f[i] = t[i]; }
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v); // u 完成后 v 才能开始
e[u].push_back(v); indeg[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push(i);
int tot = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); tot++;
for (int v : e[u]) {
f[v] = max(f[v], f[u] + t[v]); // 前驱全部完成才能开始
if (--indeg[v] == 0) q.push(v);
}
}
ll ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, f[i]); // 不是 f[n]
printf("%lld\n", ans);
return 0;
}O(n+m)。拓扑序上做一次最长路 DP，答案是 max(f[i]) 而不是 f[n]。
求 1 到 n 的最短路径条数。
cnt[]：更短则赋值，相等则累加。cnt[1] = 1 是必须的边界（空路径算一条）。分两步最稳：先 Dijkstra 定距离，再按距离升序做 DP。边权为正时「最短路图」一定是 DAG，按距离排序后每条边只会被算一次，不会重复也不会漏。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005, M = 400005;
const ll INF = 0x3f3f3f3f3f3f3f3fLL, MOD = 1000000007;
int head[N], nxt[M], to[M], cntE;
ll w[M], dis[N], cnt[N];
void add(int u, int v, ll c) {
to[++cntE] = v; w[cntE] = c;
nxt[cntE] = head[u]; head[u] = cntE;
}
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; ll c; scanf("%d%d%lld", &u, &v, &c);
add(u, v, c); add(v, u, c); // 无向带权图
}
// 第一步：Dijkstra 求出真正的距离
memset(dis, 0x3f, sizeof(dis)); dis[1] = 0;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
pq.push({0, 1});
while (!pq.empty()) {
pair<ll,int> pr = pq.top(); pq.pop();
ll d = pr.first; int u = pr.second;
if (d > dis[u]) continue;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (d + w[i] < dis[v]) { dis[v] = d + w[i]; pq.push({dis[v], v}); }
}
}
if (dis[n] >= INF / 2) { puts("0"); return 0; }
// 第二步：按距离从小到大做 DP，最短路径图一定是 DAG
vector<int> ord;
for (int i = 1; i <= n; i++) if (dis[i] < INF / 2) ord.push_back(i);
sort(ord.begin(), ord.end(), [](int a, int b) { return dis[a] < dis[b]; });
cnt[1] = 1; // 边界：到起点本身有 1 条空路径
for (int u : ord) {
if (!cnt[u]) continue;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (dis[u] + w[i] == dis[v]) // 这条边属于某条最短路
cnt[v] = (cnt[v] + cnt[u]) % MOD;
}
}
printf("%lld\n", cnt[n]);
return 0;
}O(m log m + n log n)。cnt[1] = 1 是必须的边界（空路径算一条）；不可达输出 0。
每条边有通行费，有 k 次机会把某条边的费用变 0，求 1 到 n 的最小花费。
dis[u][j] 表示到 u、已用 j 次机会。dis[v][j] = dis[u][j] + w；免费跳层 dis[v][j+1] = dis[u][j]。j < k，否则越界。min(dis[n][0..k])，不是 dis[n][k]。分层图的本质是把「状态」当成点：元组 (u, j) 就是一个新点，两种转移分别是「同层付费」和「跳层免费」。想通这一点，代码只是普通 Dijkstra。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10005;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
struct Edge { int to; ll w; };
vector<Edge> e[N];
ll dis[N][11]; // k ≤ 10，开 11 层
int main() {
int n, m, k; scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
e[u].push_back({v, w});
e[v].push_back({u, w}); // 双向边
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++) dis[i][j] = INF;
dis[1][0] = 0;
// 状态压成一个整数：id = 点号 * (k+1) + 已用次数
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
pq.push({0, 1 * (k + 1) + 0});
while (!pq.empty()) {
pair<ll,int> pr = pq.top(); pq.pop();
ll d = pr.first; int id = pr.second;
int u = id / (k + 1), j = id % (k + 1);
if (d > dis[u][j]) continue;
for (Edge ed : e[u]) {
if (d + ed.w < dis[ed.to][j]) { // 付费：留在同一层
dis[ed.to][j] = d + ed.w;
pq.push({dis[ed.to][j], ed.to * (k + 1) + j});
}
if (j < k && d < dis[ed.to][j + 1]) { // 免费：跳到下一层
dis[ed.to][j + 1] = d;
pq.push({d, ed.to * (k + 1) + j + 1});
}
}
}
ll ans = INF;
for (int j = 0; j <= k; j++) ans = min(ans, dis[n][j]); // 机会可以不用完
printf("%lld\n", ans);
return 0;
}O(km log(km))，状态数 n(k+1)。答案是 min(dis[n][0..k])——机会可以不用完。
点有点权，可重复经过点但权值只算一次，求从 1 出发能获得的最大权值和。
dfn[v]」不能写错成 low[v]。v == u，顺序反了会漏掉根。f[scc[1]]，其余 −INF；传递时判 f[u] != -INF。缩点后必须重建图，直接在原图上跑拓扑 DP 会被环卡死（环上的点入度永远减不到 0）。重建时只需处理 scc[u] != scc[v] 的边。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10005, M = 100005;
int head[N], nxt[M], to[M], cntE;
int dfn[N], low[N], stk[N], top, timer_, scc[N], scnt;
bool inStk[N];
ll val[N], sw[N]; // sw：缩点后的点权
void add(int u, int v) {
to[++cntE] = v; nxt[cntE] = head[u]; head[u] = cntE;
}
void tarjan(int u) {
dfn[u] = low[u] = ++timer_;
stk[++top] = u; inStk[u] = true;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
else if (inStk[v]) low[u] = min(low[u], dfn[v]); // 回边用 dfn[v]
}
if (low[u] == dfn[u]) {
scnt++; int v;
do {
v = stk[top--]; inStk[v] = false;
scc[v] = scnt; sw[scnt] += val[v];
} while (v != u);
}
}
vector<int> g[N];
int indeg[N];
ll f[N];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lld", &val[i]);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
add(u, v);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); // 图可能不连通
for (int u = 1; u <= n; u++) // 重建 DAG
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (scc[u] != scc[v]) { g[scc[u]].push_back(scc[v]); indeg[scc[v]]++; }
}
queue<int> q;
for (int i = 1; i <= scnt; i++) { f[i] = -1; if (!indeg[i]) q.push(i); }
f[scc[1]] = sw[scc[1]]; // 只从 1 号所在的点出发
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (f[u] > 0) f[v] = max(f[v], f[u] + sw[v]);
if (--indeg[v] == 0) q.push(v);
}
}
ll ans = 0;
for (int i = 1; i <= scnt; i++) ans = max(ans, f[i]);
printf("%lld\n", ans);
return 0;
}O(n+m)。Tarjan 线性 + 一次拓扑 DP；递归深度 ≤ n，n=10⁴ 安全。
每道题都亲手写完再提交，不要看题解抄。同一道题隔一周再写一遍，能独立写出来才算真会。
| 阶段 | 题目 | 练什么 |
|---|---|---|
| 第一周 建图与遍历 | P3916 图的遍历 | 反向建图 + DFS |
| P5318 查找文献 | 图的基本遍历 + 排序输出 | |
| P4017 最大食物链计数 | DAG 上 DP + 拓扑排序 | |
| 第二周 最短路 | P3371 单源最短路径（弱化版） | Dijkstra 入门 |
| P4779 单源最短路径（标准版） | 堆优化 + 链式前向星 | |
| P3385 负环 | SPFA 判负环 | |
| 第三周 生成树与 DP | P3366 最小生成树 | Kruskal + 并查集 |
| P1113 杂务 | DAG 最长路 / 关键路径 | |
| P1525 关押罪犯 | 二分 + 二分图判定（提高） | |
| 第四周 进阶选做 | P3387 缩点 | Tarjan SCC + 缩点 + DAG DP |
| P3388 割点 | Tarjan 求割点 | |
| P2055 假期的宿舍 | 二分图最大匹配（提高） |
| 问题 | 算法 | 复杂度 | 触发关键词 / 条件 |
|---|---|---|---|
| 遍历 / 连通块 | DFS、BFS | O(n+m) | 「能否到达」「几个块」 |
| 无权最短路 | BFS | O(n+m) | 边权全为 1、网格迷宫 |
| 任意两点最短路 | Floyd | O(n³) | n ≤ 500、要全部点对 |
| 单源最短路（非负） | Dijkstra | O(m log m) | 边权非负、n 大 |
| 单源最短路（有负权） | SPFA / Bellman-Ford | 平均 O(km) | 「收益」「补贴」「可能为负」 |
| 判负环 | SPFA + cnt | O(nm) | 「是否可能无限小」 |
| 依赖关系 / 判环 | 拓扑排序 | O(n+m) | 「先修」「顺序」「能否完成」 |
| DAG 最长路 / 计数 | 拓扑 + DP | O(n+m) | 「关键路径」「方案数」 |
| 连通全部点、总代价最小 | Kruskal / Prim | O(m log m) / O(n²) | 「修路」「铺管道」「最少花费」 |
| 二分图判定 | 染色（BFS/DFS） | O(n+m) | 「分成两组」「不能相邻」 |
| 互相可达 / 环上信息 | Tarjan SCC + 缩点 | O(n+m) | 「能回来」「可重复走」 |
| 网络瓶颈 | 割点 / 桥 | O(n+m) | 「删掉就断」「关键节点」 |
| 一一配对 | 匈牙利 | O(nm) | 「最多能配几对」 |
| 带次数限制的最短路 | 分层图 | O(k·m log) | 「k 次免费」「有状态」 |
本讲义参考王晓鹏《图论基础》（NOI 南京站培训）的知识框架，结合 NOI 大纲入门级要求与 CSP-J/S 历年考查方式编写。
例题与代码均经手算核对，若有疏漏欢迎指出。