暢通工程

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