暢通工程
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 21517 Accepted Submission(s): 9274
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
?
Source 浙大計算機研究生復試上機考試-2007年
思路:
這道題是一道純模板題,已經給你了點和邊給你連好圖了,所以,你只需要用最小生成樹的方法求解就行了(用到並查集)! 注意:這裡面還有不能夠構成聯通的圖的可能,所以,到最後要用並查集(p[i]==i)的方法判斷有幾個根節點,如果不是一個,那就輸出問好(?),否則輸出結果!
代碼:
#include
#include
#include
using namespace std;
int n,m;
int pre[110];
struct node
{
int u,v,w;
}p[10100];
int cmp(node a,node b)
{
return a.w