如何计算为所有房间部署网络的最低成本？

这个问题本质是全局最优的连通组网问题，单纯选最便宜的路由器贪心无法覆盖所有场景，而引入虚拟节点的最小生成树方法可以完美解决所有约束和成本权衡问题。

核心思路 #

我们可以把“安装路由器”这个行为转化为一个虚拟的“互联网节点”，将原问题转化为求包含该虚拟节点在内的全图最小生成树：

• 新增一个虚拟节点（比如编号为n，对应原房间编号0~n-1）。
• 给每个房间i添加一条虚拟节点到i的边，边的成本为router[i]——这条边代表“给房间i安装路由器，直接接入互联网”。
• 保留原有的所有以太网边，每条边的成本为给定的c。
• 计算这个扩展图的最小生成树（MST），MST的总权重就是满足所有约束的最小组网成本。

为什么这个方法有效？ #

1. 满足约束要求：MST必须保证所有节点（包括虚拟节点）连通，因此至少有一条虚拟节点到房间的边被选中——对应至少一个房间安装路由器，符合约束条件2。
2. 自动权衡成本：MST会在“直接装路由器”和“拉电缆连其他房间”之间选择全局最优的组合，不管是短链还是长链，只要总代价更低就会被纳入。
3. 适配链式连接：MST天然支持任意长度的连通链，只要路径成本最优。

用示例验证 #

针对题目中的示例：

• 虚拟节点编号为5，添加边：(5,0,1)、(5,1,2)、(5,2,1)、(5,3,5)、(5,4,3)
• 原有以太网边：(2,4,1)、(0,2,3)、(1,3,3)、(0,4,1)
• 计算MST时，会选中以下边：
  • (5,0,1)、(5,2,1)、(5,1,2)、(0,4,1)、(1,3,3)
• 总代价：1+1+2+1+3=8，和示例输出完全一致。

具体实现步骤 #

1. 构建扩展图：将虚拟节点与所有房间的连接边，和原有以太网边合并成一个边集。
2. 计算MST：
   • 若用Kruskal算法：将所有边按成本从小到大排序，用并查集（Union-Find）维护连通性，依次选择边，直到所有节点（包括虚拟节点）连通。
   • 若用Prim算法：从虚拟节点开始，逐步扩展到所有房间，选择当前最小成本的边加入生成树。

为什么单纯贪心选最便宜路由器不行？ #

举个反例：假设房间A路由器成本10，房间B路由器成本3，房间C路由器成本3，A-B电缆成本8，B-C电缆成本8。如果只选A的路由器，总代价是10+8+8=26；但选B和C的路由器总代价是3+3=6，显然后者更优。虚拟节点的MST方法会自动处理这类复杂的成本权衡，找到全局最优解。

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