Kruskal/Prim算法错误排查：最小生成树结果与预期不符

核心问题：未使用虚拟节点优化或处理错误 #

ABC352-E的直接生成子集内所有两两边会导致边数达到O(M*K²)（K是子集大小），不仅超时，还会因为边数过多导致计算错误。正确做法必须用虚拟节点优化：

1. 新增M个虚拟节点（编号从N+1到N+M）
2. 对第i次操作（子集S_i，权重C_i），给每个u∈S_i添加边(u, N+i)，权值为C_i
3. 在包含N+M个节点的图上跑Kruskal算法
4. 最终MST总权重需要减去所有C_i的和——因为每个虚拟节点在MST中会被一条边连接（多算一个C_i），而虚拟节点不属于原问题的图，需要剔除这部分代价

你的输出错误可能原因： #

• 未使用虚拟节点，直接枚举子集内所有两两边，导致总权重计算错误（比如当子集多次重叠时，重复计算了不必要的边）
• 使用了虚拟节点，但忘记减去sum(C_i)，导致总权重多了M个C_i的总和
• 并查集实现错误：比如路径压缩、按秩合并写错，导致连通性判断错误，选边时重复计算

Prim算法同样可以解决该问题，但需要适配虚拟节点模型：

1. 构建包含原节点和虚拟节点的邻接表，边权为C_i
2. 初始化距离数组时，要覆盖所有N+M个节点
3. 运行Prim算法后，检查所有原节点是否都被纳入MST
4. 总权重同样需要减去sum(C_i)

常见错误点： #

• 邻接表只处理了原节点之间的边，遗漏了原节点与虚拟节点的边
• 未将虚拟节点纳入Prim的遍历范围，导致无法通过虚拟节点连通原节点子集
• 计算总权重时未减去sum(C_i)，结果偏大
• 距离数组初始化错误（比如未设为无穷大），导致无法正确选择最小边

1. 先检查Kruskal的虚拟节点实现：
   • 确认是否创建了N+M个节点的并查集
   • 确认每条原节点到虚拟节点的边都被添加
   • 计算sum_C = sum(C_i)，将你的Kruskal结果减去sum_C，看是否等于预期值1202115217
2. 检查并查集代码：
   • 查找函数是否有路径压缩：find(u) { if (parent[u] != u) parent[u] = find(parent[u]); return parent[u]; }
   • 合并函数是否按秩/大小合并，避免树退化
3. 验证Prim算法：
   • 输出Prim计算的MST总权重，减去sum_C后看是否匹配预期
   • 检查是否所有原节点的距离都被更新为非无穷大（即连通）

内容的提问来源于stack exchange，提问作者Aicody