某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
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
1 #include<stdio.h>
2 #include<algorithm>
3 struct node
4 {
5 int st,en,w;
6 }mapp[
5000];
7 int set[
5000],n,m;
8 int cmp(
struct node x,
struct node y)
9 {
10 return x.w <
y.w;
11 }
12 int find(
int x)
13 {
14 if (x !=
set[x])
15 x = find(
set[x]);
16 return x;
17 }
18 int kruskal()
19 {
20 int cnt =
0;
21 for(
int i =
0; i <= n; i++
)
22 set[i] =
i;
23 for(
int i =
0; i < m; i++
)
24 {
25 int x =
find(mapp[i].st);
26 int y =
find(mapp[i].en);
27 if(x !=
y)
28 {
29 cnt +=
mapp[i].w;
30 if(x <
y)
31 set[y] =
x;
32 else set[x] =
y;
33 }
34 }
35 return cnt;
36 }
37 int main ()
38 {
39 while(~scanf(
"%d",&n)&&
n)
40 {
41 m = n*(n-
1)/
2;
42 for(
int i =
0; i < m; i++
)
43 scanf(
"%d %d %d",&mapp[i].st,&mapp[i].en,&
mapp[i].w);
44 std::sort(mapp,mapp+
m,cmp);
45 printf(
"%d\n",kruskal());
46 }
47 return 0;
48 }
1 for(i =
2; i <= m; i++
)
2 if(find(i) != find(
1))
3 flag =
0; 联通性判断 （有m个村庄）
因为之前开得数组太的小一直没过，注意m=n*(n-1)/2会很大,。
转载于:https://www.cnblogs.com/LK1994/archive/2013/05/04/3058663.html
