#include <iostream>
#include <string.h>
#include <sstream>
#include <math.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std; struct Node
{
int startPoint;
int endPoint;
int len;
bool operator <(const Node other) const
{
return len<other.len?true:false;
}
};
int findParent(int isAdded[],int point)
{
if(isAdded[point]==-)
return point;
else
return findParent(isAdded,isAdded[point]);
}
int main()
{
int n = ;
cin>>n;
while(n!=)
{
Node areaPoint[];
int totalCost = ;
if(n==)
{
cout<<totalCost<<endl;
cin>>n;
continue;
}
int isAddEd[];
int i;
for(i=;i<;i++)
isAddEd[i] = -;
int edge = ;
for(i=;i<n*(n-)/;i++)
{
cin>>areaPoint[i].startPoint>>areaPoint[i].endPoint>>areaPoint[i].len;
}
sort(areaPoint,areaPoint+n*(n-)/); for(i=;i<n*(n-)/;i++)
{
int start = areaPoint[i].startPoint;
int rear = areaPoint[i].endPoint; int startParent = findParent(isAddEd,start); int rearParent = findParent(isAddEd,rear);
//cout<<start<<" "<<rear<<" "<<startParent<<" "<<rearParent<<endl; if(startParent == rearParent)
{
continue;
}
else
{
isAddEd[startParent] = rearParent;
totalCost += areaPoint[i].len;
edge++;
if(edge==n-)
break;
}
}
cout<<totalCost<<endl;
cin>>n;
} return ;
}
- 题目描述：
-
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
- 输入：
-
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
- 输出：
-
对每个测试用例，在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
解题思路：
存储每一条边，以及对应的2个端点，按边的长度排序
对每一条边进行遍历，如果该边的2个端点的父节点相同，表示当前边不能加入，如果加入则会形成环，否则加入，并修改起点的父亲的父亲为终点的父亲。
每加入一条边，计数器加1，当计数器为n-1时结束循环，避免后面没必要的遍历。