hihocoder1098最小生成树（kruscal算法）

浏览数：30 / 时间：2015年06月08日

kruscal算法描述：

kruscal算法的思路是：最初，把所有节点都看成孤立的集合，将图中所有的边按权重从小到大排序，然后依次遍历这些边，若边的两个端点在两个不同的集合中，则合并这条边的端点所属的两个集合，直到选出n-1条边将图中的所有n个节点都合并到了同一个集合，n-1次合并就选出了n-1条边，由这n-1条边和图上的n哥节点所构成的就是我们需要的该图的最小生成树。

kruscal算法的性能依赖于边的数目，故对于稀疏图的最小生成树问题，采用kruscal算法比较优越。

我的代码：

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 #define MAXN 100005
 8 #define INF 0x7fffffff
 9 
10 struct edge
11 {
12     int u, v, w;
13     edge(int _u, int _v, int _w):u(_u),v(_v),w(_w){}
14     bool operator<(const edge &x)const
15     {
16         return w<x.w;
17     }
18 };
19 
20 vector<edge> e;
21 int n, m;
22 
23 struct unionFindSet
24 {
25     int st[MAXN];
26     void init()
27     {
28         for(int i=1; i<=n; ++i) st[i] = i;
29     }
30     int findSet(int x)
31     {
32         if(x==st[x]) return x;
33         return st[x] = findSet(st[x]);
34     }
35     void unionSet(int x, int y)
36     {
37         int sx = findSet(x), sy = findSet(y);
38         st[sx] = sy;
39     }
40 }ufs;
41 
42 int kruscal()
43 {
44     sort(e.begin(), e.end());
45     int ans = 0, cnt = 0;
46     ufs.init();
47     for(int i=0; i<e.size()&&cnt<n-1; ++i)
48     {
49         int su = ufs.findSet(e[i].u), sv = ufs.findSet(e[i].v);
50         if(su!=sv)
51         {
52             ufs.unionSet(su, sv);
53             ans += e[i].w;
54         }
55     }
56     return ans;
57 }
58 
59 int main()
60 {
61     while(cin>>n>>m)
62     {
63         e.clear();
64         while(m--)
65         {
66             int u, v, w;
67             cin>>u>>v>>w;
68             e.push_back(edge(u, v, w));
69         }
70         cout<<kruscal()<<endl;
71     }
72     return 0;
73 }