我在一次采访中被问到了下面的问题，我无法找到有效的解决办法。
问题是：
我们要建立一个网络，我们得到n个节点和m个边。边缘
是双向的，我们知道边缘的成本。所有的成本
边被保存在一个数组c中，所以c[i，j]表示
边i-j。如果节点i，j没有连接，那么C[i，j]是无限的。
现在我们也知道，有K个节点能够进行通信
无线到具有此属性的其他节点（对于无线
传输）为节点i设置无线技术需要B[i]所以
节点i以便使用无线传输到节点j的能力
这将花费B[i]为节点i和
B[j]代表j。
所以问题是找到建造
任何两个节点i，j可以通信的网络（将有
连接它们的路径）。
作为路径，我们的意思是要么有从节点i到j的边
或者我们也可以在支持
它。
很明显，我们要求最小生成树，但困难在于，例如，如果我们对节点i、j和k使用无线技术，然后我们添加可能的边i-j、i-k、j-k，但是如果我们只在i、j中使用，那么我们只有额外的边i-j，因此边取决于我们选择用于无线传输的节点。
一个简单的例子：
假设我们有4 nodes和3 edgesC[1,2]=9 , C[1,3]=3 , C[3,4]=5（其他C[i,j] are infinite）。
节点2和3支持无线技术，设置成本B[2]=2和B[3]=1。
在本例中，最低成本为：16 = 8 (for edge 1-3) + 5 (for edge 3-4) + 2 (for set up cost 2) + 1 (for set up cost in node 3).
如果我们没有在edge 2-3中使用无线技术，那么为了构建网络，我们应该包括edge 1-2和成本9，因此总成本将9+8+5 = 22.
我在寻找一个有效的算法来解决这种最小生成树问题任何帮助都将不胜感激，谢谢您的时间！!
最佳答案
首先解决最小生成树问题，这会给你一个现有的答案来尝试beat。
现在，创建另一个与原始图相同的图，向该网络添加一个新节点将所有K个节点连接到边权重等于B[i]的新节点此边表示将无线添加到节点i的成本。现在查找新图的最小生成树。节点现在可以通过这个节点连接为“wifi”。
（我假设他们告诉你哪些K个节点支持wifi，而不是你必须选择N个节点中的K个，否则如果这个新的最小生成树与新节点的连接数超过K个，你就会遇到问题）。