具有頂點權重和邊權重的最小Spanninjg樹

Question

我正在解決有關最小生成樹的問題。因此，圖中的每個節點都是一個城市，並且可能具有連接兩個節點的權重邊，這是在兩個城市之間建設公路的成本。問題主要在於告訴我們建設道路的最低成本，並讓所有的城市都有一定的聯繫。我可以通過使用Prim或kruskal算法輕鬆解決這個問題，解決我最大的問題。

棘手的部分是現在：每個城市（節點）可以有一個機場，每個機場都有一次性成本（如果你決定建造它）。如果兩個城市都有機場，您可以使用機場在兩個城市之間旅行。現在，我必須計算建設道路和機場的最低成本，以便讓所有城市相連，但我很難代表與機場與其他網絡的連接。有人可以幫我嗎？也許我對使用MST完全錯誤？

我想出的唯一解決方案是：對於每個有機場的城市，我都會將該城市與另一個有機場的城市連接起來。另外，如果建造兩個機場的成本較低，那麼建設一條道路，我會考慮它。我運行克魯斯卡爾以獲得最便宜的邊緣，但是如果克魯斯卡爾選擇了「機場」邊緣，我會將它添加到生成樹中，然後將兩個機場的成本（如果它們以前沒有建成）相加。我相信，通過在運行克魯斯卡爾時做這種動態的重量變化，我就能消除獲得最低成本的想法。

Answer 1

有兩種可能性：

1）的最佳解決方案不使用機場。在這種情況下，您可以忽略機場並照常構建最小生成樹。

2）最佳解決方案使用機場。在這種情況下，將一個虛擬節點添加到名爲「天空」的圖形中。從任何城市到「天空」的道路建設成本都是建設機場的成本。使用機場的最佳解決方案的成本是此修正圖中最小生成樹的成本。

因此，嘗試這兩個選項，並選擇最低成本。