CSP-S 提高级 · CSP 2025 提高级第一轮 第 7 题

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），任意两点之间的边权等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权为 $|7 - 3| = 4$。该图的最小生成树总权重是多少？

拿到题先别想跑 Kruskal 或 Prim 算法，8 个顶点只要 7 条边，边权最小就是 1，直接连相邻顶点成一条链，总权重就是 7。

学生容易把完全图想复杂，觉得要枚举所有边或者担心有环，其实边权规律太明显了，相邻点权值全是 1，直接连起来既连通又无环，总权重下界就是 7，根本不需要复杂算法。

考察知识点

图论 — 最小生成树 (MST)

概念定义

• 最小生成树：连通无向图的子图，包含所有顶点且边权总和最小的树（n-1 条边）。
• Kruskal 算法：按边权从小到大选边，用并查集避免成环。
• Prim 算法：从一个顶点开始，每次选择连接已选集合和未选集合的最小边。

命题视角

这道题是典型的“规律题”。命题人故意给了一个完全图，边权是两顶点编号差的绝对值，其实就是想考你对边权分布的敏感度。在完全图里，边权最小值永远是 1（相邻顶点），而 MST 只需要 n-1 条边，如果这些边权能全取到最小值 1，那总权重就是 n-1，这是理论下界。命题人就是看你能不能一眼看出这个下界，而不是让你真的去跑算法。

逐步推导

完全图 K₈，边权 w(i,j) = |i-j|。 最小可能的边权是 1（相邻顶点）。

要构成生成树需要 7 条边。若全部用权值为 1 的边：

• 1-2, 2-3, 3-4, 4-5, 5-6, 6-7, 7-8
• 这恰好是一条链，连通所有 8 个顶点
• 总权重 = 1 × 7 = 7

这是否是最小可能？每条边至少权值为 1，且至少需要 7 条边，所以最小总权重的下界就是 7。上述构造达到了这个下界，因此答案就是 7。

避坑指南

不要被“完全图”吓到，简单分析边权规律即可。8 个顶点完全图有 C(8,2)=28 条边，但 MST 只需 n-1=7 条最小边。学生最容易犯的错误是试图用 Kruskal 算法手动排序所有 28 条边，或者担心连相邻点会成环（其实连成一条链根本不成环），这都是过度思考。记住：当边权有特殊规律时，不要直接跑算法，先分析规律。本题中相邻顶点边权最小，MST 就是一条经过所有顶点的链，总权重 = n-1。

考频与趋势

图论算法在题库中共考过 26 题，覆盖 3 个考试级别（2015-2026）；逐年分布：2015 年 2 题、2016 年 1 题、2017 年 1 题、2019 年 1 题、2021 年 1 题、2024 年 1 题、2025 年 2 题、2026 年 5 题、null 年 12 题；分赛事：CSP 入门级 14 题、CSP 提高级 8 题、NOIP 提高组 初赛 4 题。最小生成树单独考过 26 题，覆盖 6 个考试级别（2009-2026）；逐年分布：2009 年 1 题、2014 年 1 题、2015 年 2 题、2023 年 1 题、2024 年 5 题、2025 年 10 题、2026 年 5 题、null 年 1 题；分赛事：GESP 八级 15 题、GESP 五级 4 题、NOIP 普及组 初赛 2 题、GESP 七级 2 题、NOIP 提高组 初赛 2 题、CSP 提高级 1 题。

预测

从数据看，2025 年 MST 考了 10 题，2026 年考了 5 题，近几年考频明显上升，且 CSP 提高级作为单选题出现，说明命题人更倾向于考基础概念和规律识别，而非复杂计算。未来可能会继续以“特殊边权规律 + 完全图/稀疏图”的形式出题，让学生快速判断下界或构造最优解，不太可能再考大规模 Kruskal 的手动模拟。暂无足够依据预测具体年份或题型变化，但建议同学重点掌握“边权规律 → 下界构造”这一解题心法。