带权无向图中Hub节点周边最小生成树求解问询

步骤1：多源最短路径计算与节点过滤 #

• 所有Hub节点作为多源点，运行多源Dijkstra算法，为每个节点计算两个值：到最近Hub的最短距离dist[u]、对应的最近Hub编号hub_id[u]。
• 遍历所有非Hub节点，如果存在至少两个不同的Hub，满足到该节点的最短距离等于dist[u]，则标记该节点为废弃节点，后续流程直接排除。

注意：这一步要确保每个有效非Hub节点仅对应唯一的归属Hub，没有歧义。

步骤2：子图拆分 #

• 对原始图进行过滤，仅保留两类节点：所有Hub节点、非废弃的非Hub节点。
• 按归属的hub_id将过滤后的节点划分为互不相交的子图，每个子图对应一个Hub的管辖范围。

注意：跨不同hub_id的边直接丢弃，不需要纳入后续计算。

步骤3：各子图最小生成树计算与成本累加 #

• 对每个子图单独运行Prim算法或者Kruskal算法计算最小生成树的总边权。
• 所有子图的MST边权之和就是最终要求的总边权成本。

之前的方案失效大概率是因为没有先完成节点归属的明确划分，就直接累加边权，容易出现跨Hub范围的边被误算，或者歧义节点没有提前排除导致归属逻辑混乱的问题。严格按照先划分再单独算MST的流程，就能覆盖所有合法场景。

你提到的两个参考示例可直接套用上述流程验证：

• 示例1按流程计算各子图MST总和为18
• 示例2按流程计算各子图MST总和为42，完全匹配预期结果。

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