hdu 1301 kruskal 最小生成树

之前已经有一个prim的解题报告了，现在就直接说krukal

其中的实现，里面就是将图中所有的边都包含进来，记录所有的边权值，然后根据边权值进行排序，然后每次都是寻找最小的那条边纳入进来，

若纳入进来的这条边当中的两个节点都已经存在现在已经生成的树当中的话，那么接着寻找下一条边。

若寻找的两个点其中有点不是生成树当中的，那么比较这两个点的父亲节点所包含的儿子的总数，总数大的则为生成树的本体，那么将其中总数小的父亲节点的父亲赋值为另一方，然后继续寻边，最后直到寻找到n-1条边即可。

代码具体如下：

View Code

 1 #include<iostream>
 2 #include<stdio.h>
 3 using namespace std;
 4 struct node
 5 {
 6   int s,e,w;       
 7 }edge[1000];
 8 int cmp(node a,node b)
 9 {
10    return a.w<b.w;    
11 }
12 int father[30],son[30];
13 int get_father(int index)
14 {
15     return index==father[index]?index:get_father(father[index]);
16 }
17 int combine(int x,int y)
18 {
19     int father1=get_father(x);
20     int father2=get_father(y);
21     if(father1==father2)
22     return 0;
23     else
24     {
25          if(son[father1]>=son[father2])
26          {
27             son[father1]+=son[father2];
28             father[father2]=father1;                             
29          }    
30          else
31          {
32             son[father2]+=son[father1];
33             father[father1]=father2;    
34          }
35        return 1;
36     }
37 }
38 int main()
39 {
40   int n;
41   while(scanf("%d",&n)!=EOF&&n)
42   {
43      int Count,k=0,weight;
44      char start,end;
45      for(int i=1;i<=n;i++)
46      {
47         father[i]=i;
48         son[i]=1;        
49      }
50      for(int i=0;i<n-1;i++)
51      {
52         getchar();
53         scanf("%c %d",&start,&Count);
54         for(int j=0;j<Count;j++)
55         {
56             getchar();
57             scanf("%c %d",&end,&weight);
58             edge[k].s=start-64;
59             edge[k].e=end-64;
60             edge[k++].w=weight;       
61         }        
62      }    
63      sort(edge,edge+k,cmp);
64      int result=0,total=0;
65      for(int i=0;i<k;i++)
66      {        
67          if(combine(edge[i].s,edge[i].e))
68          {
69              total++;
70              result+=edge[i].w;                            
71          }
72          if(total==n-1)break;
73      }                
74      printf("%d\n",result);
75   }
76   return 0;    
77 }