暢通工程2
from hdu 1863
Time limit：1s
Memory limit：32MB
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
?
這個題目，最小生成樹應用，一棵樹，需要有合理的m-1條邊將m個集合合并成為一個，我們對存在的邊從小到大遍歷，其兩端點如果屬于兩個集合，則合并，并且在合并的時候將需要的邊（后面用need表示）減去1就可以了，
#include<cstdio>
#include<algorithm>
using namespace std;
int father[105];
int find(int x){
if(father[x] == x)
return x;
return father[x] = find(father[x]);
}
struct E{
int f,t,w;
}e[50010];
bool cmp(E a,E b){
return a.w < b.w; //按照邊的權值排序
}
int n,m,x,y,need,sum;
int main(){
while(scanf("%d %d",&n,&m) && n){
for(int i = 1;i <= m;++i) father[i] = i; //初始化
need = m - 1,sum = 0;
for(int i = 1;i <= n;++i)
scanf("%d %d %d",&e[i].f,&e[i].t,&e[i].w);
sort(e + 1,e + 1 + n,cmp);
for(int i = 1;i <= n;++i){
x = find(e[i].f),y = find(e[i].t);
if(x != y) //如果不在同一集合，則合并
father[x] = y,--need,sum += e[i].w;
}
if(!need) //如果最后need等于0（已經將m個集合合并成一個集合），則輸出sum
printf("%d\n",sum);
else //否則輸出？
printf("?\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257101.html
標籤：其他
上一篇：C語言編程＞第二十三周 ⑤ 請補充main函式，該函式的功能是：求1～100（不包括100）以內所有素數的平均值。
下一篇：二進制中1的個數問題 （超詳細）