NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 28 题

（交通中断）有一个小国家，国家内有 $n$ 座城市和 $m$ 条双向的道路，每条道路连接着两座不同的城市。其中 $1$ 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第 $i(i>1)$ 个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 $i$ 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。

对于每一个城市 $i$，假定只有第 $i$ 个城市与外界交通中断，输出有多少个 城市会因此导致到首都的最短路径长度改变。

我们采用邻接表的方式存储图的信息，其中 head[x] 表示顶点 $x$ 的第一条边的编号，next[i] 表示第 $i$ 条边的下一条边的编号，point[i] 表示第 $i$ 条边的终点，weight[i] 表示第 $i$ 条边的长度。（第一空 $2$ 分，其余 $3$ 分）

#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 6000
#define MAXM 100000
#define infinity 2147483647
int head[MAXN], next[MAXM], point[MAXM], weight[MAXM];
int queue[MAXN], dist[MAXN], visit[MAXN];
int n, m, x, y, z, total = 0, answer;
void link(int x, int y, int z)
{
    total++;
    next[total] = head[x];
    head[x] = total;
    point[total] = y;
    weight[total] = z;
    total++;
    next[total] = head[y];
    head[y] = total;
    point[to

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是‘最短路径DAG’：先跑SPFA得dist[]，再只保留满足dist[x]+w==dist[y]的边，对每个i在DAG里删点做BFS，统计还能到的点数。

最容易掉进两个坑：一是把松弛条件写成<=或>=，导致把不在最短路上的边也放进DAG，计数偏大；二是SPFA出队后忘记visit[x]=0，队列里会死循环或漏更新。另外别忘了双向边正反都要存，删除i时要用point[j]!=i判断，别把i的邻居误删。

这道题考什么

考查最短路径算法（SPFA）的应用、最短路径DAG的构造与遍历、以及通过删除关键点统计影响范围。属于图论与算法综合题，在NOIP提高组初赛里反复出现。

知识点人话版

• SPFA：队列优化的Bellman-Ford，适合有负权但无负环的图，能动态更新距离。
• 最短路径DAG：把所有满足dist[x]+w==dist[y]的边连起来，就得到一张有向无环图，它包含了所有最短路。
• BFS在DAG上：只走DAG里的边，从首都出发能到多少城市，就是删除点后仍可达的数量。

命题人怎么挖坑

命题人喜欢在三个地方设陷阱： 1. 松弛条件：把<写成<=或>=，就会把非最短路边也放进DAG，导致答案偏大。 2. SPFA出队标记：忘记visit[x]=0，队列里会重复处理，甚至死循环。 3. 双向边删除判断：每条边正反存两次，删除i时要用point[j]!=i，别把i的邻居误删。

拿到题先想什么→一步步推

第一步：跑SPFA求dist[]

• 初始化dist[1]=0，其余为无穷大。
• 队列里先放1，visit[1]=1。
• 每次出队x，遍历x的邻接边j：若dist[x]+weight[j]<dist[point[j]]就更新dist[point[j]]；如果point[j]还没入队（visit=0），就入队并标记visit=1。
• 关键点：出队后必须visit[x]=0，否则下次其他节点更新x时x还在队列里，会重复处理。

第二步：构造最短路径DAG

• 对每条边j（从x到point[j]），只有当dist[x]+weight[j]==dist[point[j]]时，这条边才在最短路DAG上。
• 注意：松弛条件<和DAG条件==是两个不同的判断，别混用。

第三步：对每个城市i（i>1）做BFS

• 重新初始化队列、visit数组，visit[1]=1，把1入队。
• 在BFS里遍历x的邻接边j，但只允许走：

1. point[j]!=i（跳过被删除的城市） 2. weight[j]+dist[x]==dist[point[j]]（保证在DAG上） 3. visit[point[j]]==0（没访问过）

• 满足条件的点入队，visit置1。
• BFS结束后，统计visit为1的城市数量，减去1（首都本身），就是答案。

逐空详解

(1) dist[1]=0：起点到自身的距离为0，这是SPFA初始化的标准写法。

(2) 松弛条件：dist[x]+weight[j]<dist[point[j]]。等价写法还有dist[point[j]]>dist[x]+weight[j]。不能写成<=，因为<=会把相等（已在最短路DAG上）的边也放进松弛队列，导致重复更新。

(3) visit[x]=0：SPFA出队后清除标记，允许后续再次入队。这与Dijkstra的永久标记不同，是本题必填项。

(4) DAG边判断：weight[j]+dist[x]==dist[point[j]]。两边顺序可互换，但必须用==，不能用<或>。

(5) 更新dist：dist[point[j]] = weight[j] + dist[x]。注意这里是在BFS里，其实dist已经求好了，这一步只是形式上写出来，表示沿DAG边更新距离（或理解为标记访问）。

易错点再强调

• 松弛条件：<是严格小于，==是DAG判断，千万别混淆。
• SPFA出队标记：visit[x]=0必写，否则队列会爆或死循环。
• 双向边：link函数里每条无向边存两次，删除i时要用point[j]!=i，别用head[x]!=i这种错误判断。
• BFS条件：三个条件缺一不可，少一个就会把不在DAG上的边或i的邻居算进去。

考频与趋势

• 队列：题库共考46题，2024年12题、2025年13题、2026年9题，热度持续上升。
• 图的存储：32题，2024年10题、2025年10题，链式前向星是高频考点。
• 图论算法：26题，2026年5题、2025年2题，SPFA/Dijkstra在初赛里常考。
• 最短路径：35题，2025年7题、2026年7题，本题正是典型的最短路径DAG应用。
• 图的遍历：仅4题，但2016、2017、2023年都有，说明这类‘删点后统计可达’的遍历题不会消失。

预测

从近年数据看，队列、图的存储、最短路径在2024-2026年持续高热，图的遍历题虽少但稳中有升。未来NOIP提高组初赛很可能继续考‘在最短路径DAG上删点/删边后统计影响’这类组合题，或者把BFS/DFS与最短路径DAG结合，要求判断某点是否在最短路径上、删除后是否仍可达等。暂无足够依据预测具体年份，但这类题型值得重点巩固。

总结

这道题的解题主线非常清晰：SPFA求dist → 只保留==的边构成DAG → 对每个i在DAG里做BFS统计可达点数。填空处分别对应SPFA初始化、松弛条件、出队标记、DAG边判断和更新操作。记住三个易错点（<与==的区别、visit出队清零、双向边删除判断），就能稳稳拿满分。