最小生成树变异算法
Minimum Spanning tree variation algorithm
我在面试中被问到以下问题，我无法找到有效的解决方案。
这是问题所在：
We want to build a network and we are given n nodes and m edges. Edges
are bidirectional and we know the cost of the edge. All the costs of
the edges are hold in an array C, so C[i,j] which denotes the cost of
the edge i-j. If nodes i,j are not connected then C[i,j] is infinite.
Now we also know that exactly K of the nodes are able to communicate
wireless to other nodes which have also this property (for wireless
transmission). To set up wireless technology to node i costs B[i]. So
node i in order to use the ability of wireless transmission to node j
this will costs B[i] to set up the wireless technology to node i and
B[j] for j.
So the question is to find the minimum cost required to build the
network where any two nodes i,j could communicate (there will be a
path connecting them).
As path we mean that either there are edges that lead from node i to j
or we can also use wireless transmission between nodes that support
it.
很明显，它要求最小生成树，但困难在于，例如，如果我们对节点 i、j 和 k 使用无线技术，那么我们添加可能的边 i-j、i-k、j-k，但如果我们仅使用i,j 然后我们只有额外的边 i-j 所以边取决于我们选择用于无线传输的节点。
一个简单的例子：
假设我们有 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 中使用无线技术，那么要构建网络，我们应该包括 edge 1-2，成本为 9，因此总成本为 9+8+5 = 22.
我正在为这种最小生成树问题寻找一种有效的算法。任何帮助将不胜感激，感谢您抽出宝贵时间！！
首先解决最小生成树问题，这给了你一个尝试击败的现任答案。
现在，创建另一个与原始图相同的图，向该网络添加一个新节点。将所有 K 个节点连接到这个边权重等于 B[i] 的新节点。这条边表示向节点 i 添加无线的成本。现在找到新图的最小生成树。节点现在可以通过此节点连接为 "wifi".
（我假设他们告诉你哪些 K 个节点支持 wifi，而不是说你必须选择 N 个节点中的 K 个，否则如果这个新的最小生成树有超过 K 个连接到新节点)).
我在面试中被问到以下问题，我无法找到有效的解决方案。
这是问题所在：
We want to build a network and we are given n nodes and m edges. Edges are bidirectional and we know the cost of the edge. All the costs of the edges are hold in an array C, so C[i,j] which denotes the cost of the edge i-j. If nodes i,j are not connected then C[i,j] is infinite.
Now we also know that exactly K of the nodes are able to communicate wireless to other nodes which have also this property (for wireless transmission). To set up wireless technology to node i costs B[i]. So node i in order to use the ability of wireless transmission to node j this will costs B[i] to set up the wireless technology to node i and B[j] for j.
So the question is to find the minimum cost required to build the network where any two nodes i,j could communicate (there will be a path connecting them).
As path we mean that either there are edges that lead from node i to j or we can also use wireless transmission between nodes that support it.
很明显，它要求最小生成树，但困难在于，例如，如果我们对节点 i、j 和 k 使用无线技术，那么我们添加可能的边 i-j、i-k、j-k，但如果我们仅使用i,j 然后我们只有额外的边 i-j 所以边取决于我们选择用于无线传输的节点。
一个简单的例子：
假设我们有 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 中使用无线技术，那么要构建网络，我们应该包括 edge 1-2，成本为 9，因此总成本为 9+8+5 = 22.
我正在为这种最小生成树问题寻找一种有效的算法。任何帮助将不胜感激，感谢您抽出宝贵时间！！
首先解决最小生成树问题，这给了你一个尝试击败的现任答案。
现在，创建另一个与原始图相同的图，向该网络添加一个新节点。将所有 K 个节点连接到这个边权重等于 B[i] 的新节点。这条边表示向节点 i 添加无线的成本。现在找到新图的最小生成树。节点现在可以通过此节点连接为 "wifi".
（我假设他们告诉你哪些 K 个节点支持 wifi，而不是说你必须选择 N 个节点中的 K 个，否则如果这个新的最小生成树有超过 K 个连接到新节点)).