HDOJ1233 ( 还是畅通工程 ) 【最小生成树，kruscal】

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define N 101
 6 typedef struct{
 7     int x,y;
 8     int len;
 9 }EDGE;
10 int map[N][N],set[N],n;
11 EDGE edge[N*N];
12 int cmp(const EDGE& a,EDGE& b)
13 {
14     return a.len<b.len;
15 }
16 int FindSet(int a)
17 {
18     return set[a];
19 }
20 void MergeSet(int a,int b)
21 {
22     int i;
23     for (i=1;i<=n;i++)
24         if(set[i]==a)
25             set[i]=b;
26 }
27 int main()
28 {
29     int i,p,sum,m,f,t;
30     while (scanf("%d",&n),n)//n为村庄个数
31     {
32         //初始化map
33         memset(map,0,sizeof(map));
34         //最多m条边
35         m=(n*(n-1))>>1;
36         //初始化set
37         for (i=1;i<=n;i++)    set[i]=i;    
38         //构建map
39         for (i=0;i<m;i++)    scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].len);
40         //已经选取的点的个数
41         p=0;
42         //路径总长度
43         sum=0;
44         //对边进行排序
45         sort(edge,edge+i,cmp);
46         for (i=0;i<m&&p!=n;i++)
47         {
48             //查找当前边的起始点是否在同一个集合中
49             f=FindSet(edge[i].x);
50             t=FindSet(edge[i].y);
51             if(f!=t)
52             {
53                 MergeSet(f,t);
54                 p++;
55                 sum+=edge[i].len;
56             }
57         }
58         printf("%d\n",sum);
59     }
60     return 0;
61 }