具有顶点权重和边权重的最小生成树
Minimum Spanninjg Tree with vertex weight and edge weight
我在解决有关最小生成树的问题时遇到了一些麻烦。所以图中的每个节点都是一个城市，并且可能有连接两个节点的权重边，这就是在两个城市之间修路的成本。问题基本上是告诉建设道路的最低成本，并以某种方式连接所有城市。我可以通过使用 Prim 或 kruskal 算法轻松解决这个问题来解决我最大问题的这个子问题。
现在棘手的部分来了：每个城市（节点）都可以有一个机场，每个机场都有一次性成本（如果你决定建造它）。如果两个城市都有机场，您可以使用机场在两个城市之间旅行。现在我必须计算建设道路和机场的最低成本，以便将所有城市连接起来，但我很难用网络的其余部分来表示与机场的连接。有人可以帮我吗？也许我对使用 MST 的看法完全错误？
我想到的唯一解决方案是：对于每个有机场的城市，我将把该城市与另一个有机场的城市连接起来。另外，如果建设两个机场的成本低于建设一条道路，我会考虑。我 运行 kruskal 以获得最便宜的边缘，但如果 kruskal 选择 "airport" 边缘，我会将其添加到生成树中，然后将两个机场的成本设为 0（如果它们尚未建成过去）。我相信，通过在 运行ing kruskal 时进行这种动态权重变化，我正在破坏获得最低成本的想法。
有两种可能：
1) 最优解不使用机场。在这种情况下，您可以忽略机场并像往常一样构造最小生成树。
2) 最佳解决方案使用机场。在这种情况下，向名为 "sky" 的图中添加一个虚拟节点。修建一条从任何城市到 "sky" 的道路的成本就是建造机场的成本。使用机场的最佳解决方案的成本是该修正图中最小生成树的成本。
因此请尝试这两个选项并选择最低成本。
我在解决有关最小生成树的问题时遇到了一些麻烦。所以图中的每个节点都是一个城市，并且可能有连接两个节点的权重边，这就是在两个城市之间修路的成本。问题基本上是告诉建设道路的最低成本，并以某种方式连接所有城市。我可以通过使用 Prim 或 kruskal 算法轻松解决这个问题来解决我最大问题的这个子问题。
现在棘手的部分来了：每个城市（节点）都可以有一个机场，每个机场都有一次性成本（如果你决定建造它）。如果两个城市都有机场，您可以使用机场在两个城市之间旅行。现在我必须计算建设道路和机场的最低成本，以便将所有城市连接起来，但我很难用网络的其余部分来表示与机场的连接。有人可以帮我吗？也许我对使用 MST 的看法完全错误？
我想到的唯一解决方案是：对于每个有机场的城市，我将把该城市与另一个有机场的城市连接起来。另外，如果建设两个机场的成本低于建设一条道路，我会考虑。我 运行 kruskal 以获得最便宜的边缘，但如果 kruskal 选择 "airport" 边缘，我会将其添加到生成树中，然后将两个机场的成本设为 0（如果它们尚未建成过去）。我相信，通过在 运行ing kruskal 时进行这种动态权重变化，我正在破坏获得最低成本的想法。
有两种可能：
1) 最优解不使用机场。在这种情况下，您可以忽略机场并像往常一样构造最小生成树。
2) 最佳解决方案使用机场。在这种情况下，向名为 "sky" 的图中添加一个虚拟节点。修建一条从任何城市到 "sky" 的道路的成本就是建造机场的成本。使用机场的最佳解决方案的成本是该修正图中最小生成树的成本。
因此请尝试这两个选项并选择最低成本。