題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1863

暢通工程

Problem Description

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

?

?

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

?

思路：最小生成樹，Kruskal算法。

#include<iostream> #include<cstring> #include<queue> #include<cstdio> #include<algorithm> #define ll long long using namespace std; int pre[1000000]; int find(int x) {int r=x;while(pre[r]!=r)r=pre[r];return r; } int join(int x,int y) {int fx=find(x),fy=find(y);if(fx!=fy)pre[fx]=fy; } struct stu{int x,y,z; }stu1[1000]; bool cmp(stu a,stu b)//按權值排序 {return a.z<b.z; } int main() {int n,m;while(scanf("%d %d",&n,&m)!=EOF)//n是道路條數 {if(n==0) break;for(int i=1;i<=m;i++)//注意i<=m {pre[i]=i;}for(int i=1;i<=n;i++)scanf("%d %d %d",&stu1[i].x,&stu1[i].y,&stu1[i].z);sort(stu1+1,stu1+n,cmp);//按z從小到大排序，從1開始排序int sum=0;//成本 int r=1;//連接村莊個數 for(int i=1;i<=n;i++)//對每條路連接的兩個村莊進行判斷，如果兩個村莊已經連接過，不進行處理，如果兩個村莊還沒連接，則將其連接。 {if(find(stu1[i].x)!=find(stu1[i].y)){join(stu1[i].x,stu1[i].y);sum=sum+stu1[i].z;r++;}if(r==m)//全部連接則跳出循環 break; }if(r==m)//遍歷完每一條路也不一定全部連接，路可能不夠 printf("%d\n",sum); else puts("?"); }return 0; }

?

總結

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

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