1 #include<cstdio>
2 #include<algorithm>
3 using namespace std;
4 int per[
111],n;
5 struct node{
6 int a,b;
7 int dis;
8 }x[
5005];
9 bool cmp(node a,node b)
10 {
11 return a.dis<
b.dis;
12 }
13 void init()
14 {
15 for(
int i =
1;i <= n;i++
)
16 per[i]=
i;
17 }
18
19 int find(
int x)
20 {
21 if(x!=
per[x])
22 {
23 per[x]=
find(per[x]);
24 }
25 return per[x];
26 }
27 bool join(
int a,
int b)
28 {
29 int x=find(a),y=
find(b);
30 if(x!=
y)
31 {
32 per[y]=
x;
33 return 1;
34 }
35 return 0;
36 }
37 int main()
38 {
39 int m,a,b,c;
40 while(scanf(
"%d",&
n),n)
41 {
42 int sum =
0;
43 int cnt =
0;
44 init();
45 m = n*(n-
1)/
2;
46 for(
int i =
0;i < m;i++
)
47 {
48 scanf(
"%d %d %d",&a,&b,&
c);
49 x[i].a=
a;
50 x[i].b=
b;
51 x[i].dis=
c;
52 }
53 sort(x,x+
m,cmp);
54 for(
int i =
0;cnt < n-
1 ;i++
)
55 {
56 if(join(x[i].a,x[i].b))
57 {
58 sum +=
x[i].dis;
59 cnt ++
;
60 }
61 }
62 printf(
"%d\n",sum);
63 }
64 return 0;
65 }
View Code
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
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
Sample Output
3
5
Huge input, scanf is recommended.
转载于:https://www.cnblogs.com/llal/p/5732108.html
相关资源：JAVA上百实例源码以及开源项目
