并查集+Kruskal
1 /*
2 * Problem: 最小生成树
3 * Author: Xu Fei
4 * Time: 2010.8.3 14:58
5 * Method: Kruskal
6 */
7 #include<iostream>
8 #include<cstdio>
9 using namespace std;
10
11 const int MaxN=100,MaxM=10000;
12
13 struct edge
14 {
15 int x,y,c;
16 }E[MaxM];
17 int N,M;
18 int Ans;
19 int P[MaxN];
20 int H[MaxN];
21
22 void init()
23 {
24 int i;
25 scanf("%d%d",&N,&M);
26 for(i=1;i<=M;++i)
27 {
28 scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].c);
29 }
30 }
31 inline void swap(edge &a,edge &b)
32 {
33 edge tmp;
34 tmp=a;
35 a=b;
36 b=tmp;
37 }
38 void qsort(int s,int t)
39 {
40 int i=s,j=t,mid;
41 mid=E[(i+j)>>1].c;
42 while(i<=j)
43 {
44 while(E[i].c < mid)
45 i++;
46 while(E[j].c > mid)
47 j--;
48 if(i<=j)
49 {
50 swap(E[i],E[j]);
51 i++;
52 j--;
53 }
54 }
55 if(s<j)
56 qsort(s,j);
57 if(i<t)
58 qsort(i,t);
59 }
60 inline int Find(int x)
61 {
62 if(x != P[x])
63 P[x]=Find(P[x]);
64 return P[x];
65 }
66 void change(int x,int y)
67 {
68 if(H[x] > H[y])
69 P[y]=x;
70 else if(H[y] > H[x])
71 P[x]=y;
72 else
73 {
74 H[x]++;
75 P[y]=x;
76 }
77 }
78 void solve()
79 {
80 int i,k,x,y;
81 qsort(1,M);
82 for(i=1;i<=N;++i)
83 P[i]=i,H[i]=1;
84 Ans=k=0;
85 for(i=1;i<=M;++i)
86 {
87 x=Find(E[i].x);
88 y=Find(E[i].y);
89 if(x != y)
90 {
91 Ans+=E[i].c;
92 k++;
93 if(k == N-1)
94 break;
95 change(x,y);
96 }
97 }
98 printf("%d\n",Ans);
99 }
100 int main()
101 {
102 init();
103 solve();
104 return 0;
105 }
posted on 2010-08-03 14:59
xfstart07 阅读(130)
评论(0) 编辑 收藏 引用 所属分类:
算法学习 、
图论