我在解决有关最小生成树的问题时遇到了一些麻烦。因此，图中的每个节点都是一个城市，并且可能具有连接两个节点的权重边，这就是在两个城市之间修建道路的成本。问题基本上是告诉人们修路的最低成本，并使所有城市都以某种方式连接。我可以通过使用Prim或kruskal算法轻松解决此最大问题的子问题。
现在最棘手的部分是：每个城市（节点）都可以有一个机场，而每个机场都有一次成本（如果您决定建造）。如果两个城市都有机场，则可以使用机场在两个城市之间旅行。现在，我必须计算建造道路和机场的最低成本，以使所有城市都连接起来，但是我很难用网络的其余部分来表示与机场的连接。有人可以帮我吗？也许我对使用MST是完全错误的？
我想出的唯一解决方案是：对于每个有机场的城市，我都会将该城市与另一个有机场的城市连接起来。另外，如果建造两个机场的成本较低，那么建造道路的成本也应考虑在内。我运行kruskal是为了获得最便宜的边缘，但是如果kruskal选择“机场”边缘，我会将其添加到生成树中，然后将这两个机场的成本设为0（如果它们以前没有建造过）。我相信，通过在运行kruskal时进行动态权重更改，我正在破坏获得最低成本的想法。