題目描述

省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可）。經過調查評估，得到的統計表中列出了有可能建設公路的若干條道路的成本。現請你編寫程序，計算出全省暢通需要的最低成本。

輸入

測試輸入包含若干測試用例。每個測試用例的第1行給出評估的道路條數 N、村莊數目M (N, M < =100 )；隨后的 N 行對應村莊間道路的成本，每行給出一對正整數，分別是兩個村莊的編號，以及此兩村莊間道路的成本（也是正整數）。為簡單起見，村莊從1到M編號。當N為0時，全部輸入結束，相應的結果不要輸出。

輸出

對每個測試用例，在1行里輸出全省暢通需要的最低成本。若統計數據不足以保證暢通，則輸出“?”。

樣例輸入

3 4 1 2 1 2 3 2 3 4 3 2 4 1 2 1 3 4 2 0 5

樣例輸出

6 ?

?

#include <iostream> #include <algorithm> #include <vector>using namespace std;const int maxn = 100+10; const int inf = 1000000000;int a, b; //村莊數目//kruskal struct edge {int u, v, dis; }E[maxn];int father[maxn]; int find_father(int x) {int a = x;while(x != father[x]){x = father[x];}while(a != father[a]){int z = a;a = father[a];father[z] = x;}return x; }bool cmp(edge a, edge b) {return a.dis < b.dis; }int kruskal(int n, int m) {int ans = 0, num_edge = 0;for(int i = 1; i <= n; i++){father[i] = i;}sort(E, E+m, cmp);for(int i = 0; i < m; i++){int fa = find_father(E[i].u);int fb = find_father(E[i].v);if(fa != fb){father[fa] = fb;ans += E[i].dis;num_edge++;if(num_edge == n - 1) break;}}if(num_edge != n - 1){return -1;}else return ans; }int main() {while(scanf("%d%d", &b, &a) && b){for(int i = 0; i < b; i++){int a, b, c;scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].dis);}int ans = kruskal(a, b);if(ans == -1) printf("?\n");else printf("%d\n", ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的Codeup-问题 C: 畅通工程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。