在接受采访时我被问到以下问题，我无法找到有效的解决方案 .
这是问题所在：
我们想 Build 一个网络，我们给了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，那么我们添加可能的边缘ij，ik，jk但是如果我们仅在i，j中使用那么我们只有额外的边缘ij，所以边缘取决于我们选择用于无线传输的节点 .
一个简单的例子：
假设我们有 4 nodes 和 3 edges C[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).
如果我们没有在边缘2-3中使用无线技术然后 Build 网络，我们应该包含成本为9的 edge 1-2 ，因此总成本将为 9+8+5 = 22.
我正在寻找一种有效的算法来解决这种最小生成树问题 . 任何帮助将不胜感激，谢谢你的时间！
1 回答
首先解决最小生成树问题，这为您提供了尝试节拍的现有答案 .
现在，创建与原始图形相同的另一个图形，向该网络添加新节点 . 将所有K个节点连接到边缘权重等于B [i]的新节点 . 此边缘表示向节点i添加无线的成本 . 现在找到新图的最小生成树 . 节点现在可以通过此节点连接为“wifi” .
（我假设他们告诉你哪些K节点支持wifi，而不是你必须选择N个节点中的K，否则如果这个新的最小生成树有超过K个连接到新节点，你就会遇到问题）） .