1 #include<stdio.h>
2 #include<algorithm>
3 struct Edge
4 {
5 int u,v,w;
6 }edge[
10010];
7 int n,m,sett[
110];
8 int cmp(
const struct Edge x,
const struct Edge y)
9 {
10 return x.w <
y.w;
11 }
12 int ffind(
int x)
13 {
14 if(x !=
sett[x])
15 x =
ffind(sett[x]);
16 return x;
17 }
18 int kruskal()
19 {
20 int i;
21 for(i =
1; i <= n; i++
)
22 sett[i] =
i;
23 std::sort(edge, edge+
m, cmp);
24 int cnt =
0;
25 for(i =
0; i < m; i++
)
26 {
27 int x=
ffind(edge[i].u);
28 int y=
ffind(edge[i].v);
29 if(x!=
y)
30 {
31 sett[x] =
y;
32 cnt +=
edge[i].w;
33 }
34 }
35 return cnt;
36 }
37 int main ()
38 {
39 while(~scanf(
"%d %d",&n,&
m))
40 {
41 for(
int i =
0;i < m; i++
)
42 scanf(
"%d %d %d",&edge[i].u,&edge[i].v,&
edge[i].w);
43 printf(
"%d\n",kruskal());
44 }
45 return 0;
46 }
转载于:https://www.cnblogs.com/LK1994/archive/2013/04/13/3019282.html
