HDOJ1863 ( 畅通工程 ) 【最小生成树，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 set[N],n,r;
11 EDGE edge[N*N];
12 int cmp(const EDGE& a,EDGE& b)
13 {
14     return a.len<b.len;
15 }
16 void MergeSet(int a,int b)
17 {
18     int i;
19     for (i=1;i<=n;i++)
20         if(set[i]==a)
21             set[i]=b;
22 }
23 int main()
24 {
25     int i,p,sum,f,t;
26     while (scanf("%d",&r),r)//n为村庄个数
27     {
28         scanf("%d",&n);
29         //初始化set
30         for (i=1;i<=n;i++)    set[i]=i;
31         //读取边数
32         for (i=0;i<r;i++)    scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].len);
33         //已经选取的点的个数
34         p=0;
35         //路径总长度
36         sum=0;
37         //对边进行排序
38         sort(edge,edge+i,cmp);
39         for (i=0;i<r&&p!=n-1;i++)
40         {
41             //查找当前边的起始点是否在同一个集合中
42             f=set[edge[i].x];
43             t=set[edge[i].y];
44             if(f!=t)
45             {
46                 MergeSet(f,t);
47                 p++;
48                 sum+=edge[i].len;
49             }
50         }
51         if(p!=n-1)
52             printf("?\n");
53         else
54             printf("%d\n",sum);
55     }
56     return 0;
57 }