根据《畅通工程》系列中的某题代码直接改的，忘记具体哪道了。
Problem : 1863 ( 畅通工程 ) Judge Status : AcceptedRunId : 5940637 Language : C++ Author : qq1203456195Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
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 }
转载于:https://www.cnblogs.com/CheeseZH/archive/2012/05/13/2498590.html
相关资源：数据结构—成绩单生成器
