克鲁斯卡尔

 1 #define maxn 100
 2 #define maxm 5000
 3 struct edge
 4 {
 5     int u,v;
 6     double w;
 7 }edges[maxm];
 8 int parent[maxm];
 9 int u,v,i,j;
10 void ufset()
11 {
12     memset(parent,-1,sizeof(parent));
13 }
14 int find(int x)
15 {
16     int s;
17     for(s=x;parent[s]>=0;s=parent[s])
18         ;
19     while(s!=x)
20     {
21         int tmp=parent[x];
22         parent[x]=s;
23         x=tmp;
24     }
25     return s;
26 }
27 void union(int R1,int R2)
28 {
29     int r1=find(R1),r2=find(R2);
30     int tmp=parent[r1]+parent[r2];
31     if(parent[r1]>parent[r2])
32     {
33         parent[r1]=r2;
34         parent[r2]=tmp;
35     }
36     else
37     {
38         parent[r2]=r1;
39         parent[r1]=tmp;
40     }
41 }
42 bool cmp(edge aa,edge bb)
43 {
44     return aa.w<bb.w;
45 }
46 int kruskal()
47 {
48     double sumweight;
49     int num=0;
50     ufset();
51     for(i=0;i<m;++i)
52     {
53         u=edges[i].u;    v=edges[i].v;
54         if(find(u)!=find(v))
55         {
56             sumweight+=edges[i].w; num++;
57             union(u,v);
58         }
59         if(num>=n-1) break;
60     }
61     return sumweight;
62 }