某省調查鄉村交通狀況，得到的統計表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可），并要求鋪設的公路總長度為最小。請計算最小的公路總長度。

輸入描述:

    測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數目N ( 100 )；隨后的N(N-1)2行對應村莊間的距離，每行給出一對正整數，分別是兩個村莊的編號，以及此兩村莊間的距離。為簡單起見，村莊從1到N編號。     當N為0時，輸入結束，該用例不被處理。

輸出描述:

    對每個測試用例，在1行里輸出最小的公路總長度。

示例1

輸入

3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

輸出

3
5

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define N 10000
int father[N];
int height[N];
//最小生成樹
//n個頂點n-1條邊 每個結點都能連通且權值之和最小
//建立并查集
//所有邊按從小到大遍歷每條邊
//x y屬于同一集合 忽略 不在，該邊記錄到總和中
struct Edge{int x;int y;int weight;
};
//并查集
//初始化 用一個數組father 編號i
void Init(int n){for (int i = 1; i <= n; ++i) {father[i]=i;}
}
//查
int find(int n){//找祖先if(n!=father[n]){//return find[father[n]];//爸爸的爸爸//優化 將結點的父親改為祖先father[n]=find(father[n]);}return father[n];
}//并
void Union(int x,int y,int weight,int &total){// 一個根到另一個根x=find(x);y=find(y);if(x!=y){total+=weight;}if(height[x]<height[y]){father[x]=y;}else if (height[x] > height[y]) {//x當父親father[y] = x;} else {father[y] = x;++height[x];}
}
bool compare(Edge lhs,Edge rhs){return lhs.weight<rhs.weight;
}
int main() {int n;while (scanf("%d",&n)!=EOF){//第一行if(n==0){break;}Init(n);vector<Edge> vec;for (int i = 0; i < n*(n-1)/2; ++i) {//n*(n-1)/2行數據Edge edge;scanf("%d%d%d",&edge.x,&edge.y,&edge.weight);//每讀一行vec.push_back(edge);//邊讀完}sort(vec.begin(),vec.end(), compare);//權值大小排序int total=0;for (int i = 0; i < n*(n-1)/2; ++i) {Union(vec[i].x,vec[i].y,vec[i].weight,total);//合并 如果兩個已連 忽略}printf("%d\n",total);}return 0;
}