GESP 八级 · GESP 202606 C++ 八级 第 9 题

有向非负权图边为 $(1,2,4)$、$(1,3,2)$、$(2,3,1)$、$(2,4,5)$、$(3,4,8)$、$(3,5,10)$、$(4,5,2)$。该图最小生成树的总权值为（ ）。

最小生成树：Prim（加点法，O(n²)或O(mlog n)）、Kruskal（加边法，O(mlog m)）。Kruskal需用并查集判环。

Kruskal算法需按边权排序，用并查集判断是否形成环。Prim算法适用于稠密图，Kruskal适用于稀疏图。

【考点】最小生成树（MST）｜有向图与无向图的转换｜Kruskal算法

🎯 考纲定位：本考点位于 GESP 7-9 级图论模块，命题人刻意用"有向图"包装 MST 概念，卡住考生对算法适用场景的模糊认知——8 级难度下，识别"图的方向性是否影响算法选择"是核心区分点。

🧠 解题思维：看到"有向图"+"最小生成树"应立刻警觉：MST 定义仅针对无向图。正确路径是先将每条有向边视为无向边处理，再用 Kruskal 按权排序贪心选边。关键观察：5 个顶点需选 4 条边，按权从小到大依次加入且不构成环。排序后前四条有效边为 (2,3,1)、(1,3,2)、(4,5,2)、(2,4,5)，总权 1+2+2+5=10。

🪤 陷阱拆解：选项 A(7) 来自误把 (1,2,4)、(1,3,2)、(2,3,1)、(4,5,2) 直接相加，忽略了"生成树"必须连通所有顶点且无环；选项 B(8) 是仅取最小四条边但不验证连通性；选项 C(9) 则是错误地选了 (1,2,4) 替换 (2,4,5)。命题人最阴险之处在于题干强调"有向图"，诱导考生尝试有向图的最小生成树（如 Chu-Liu/Edmonds 算法），却忘了 MST 本质是无向概念，导致方向性思维干扰。

🔄 反命题思维：若将题意改为"求有向图的最小生成树（arborescence）"，则需指定根节点并求最小入边集，答案会完全不同。刷到此类题时，先问自己"题目要求的是无向 MST 还是有向 arborescence？"——这是区分考点的核心。