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

Input測試輸入包含若干測試用例。每個測試用例的第1行給出評估的道路條數 N、村莊數目M ( < 100 )；隨后的 N?
行對應村莊間道路的成本，每行給出一對正整數，分別是兩個村莊的編號，以及此兩村莊間道路的成本（也是正整數）。為簡單起見，村莊從1到M編號。當N為0時，全部輸入結束，相應的結果不要輸出。?
Output對每個測試用例，在1行里輸出全省暢通需要的最低成本。若統計數據不足以保證暢通，則輸出“?”。?
Sample Input

3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100

Sample Output

3 ?


這題是也是一個并查集。略微加了點東西，適用于并查集入門
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define maxn 1010 7 int a[maxn]; 8 struct node { 9 int x,y,cost; 10 } qu[maxn]; 11 int find(int r) { 12 while(r!=a[r]) r=a[r]; 13 return r; 14 } 15 int cmp(node a,node b) { 16 return a.cost<b.cost; 17 } 18 int main() { 19 int n,m; 20 while(scanf("%d%d",&n,&m)!=EOF) { 21 if (n==0) break; 22 for (int i=1 ; i<=m ; i++) a[i]=i; 23 for (int i=0 ; i<n ; i++) { 24 scanf("%d%d%d",&qu[i].x,&qu[i].y,&qu[i].cost); 25 } 26 sort(qu,qu+n,cmp); 27 int ans=0; 28 node b; 29 for (int i=0 ; i<n ; i++) { 30 b=qu[i]; 31 int nx=find(b.x); 32 int ny=find(b.y); 33 if (nx!=ny) { 34 a[nx]=ny; 35 ans+=b.cost; 36 } 37 } 38 int flag=1; 39 for (int i=1 ; i<=m ; i++) { 40 if (find(1)!=find(i)) { 41 flag=0; 42 break; 43 } 44 } 45 if (flag) printf("%d\n",ans); 46 else printf("?\n"); 47 } 48 return 0; 49 }

?

?

轉載于:https://www.cnblogs.com/qldabiaoge/p/8507641.html

總結

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

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