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

简介:
Code 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 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 }
复制代码

 


本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/05/12/2497640.html,如需转载请自行联系原作者

相关文章
|
8月前
|
算法 测试技术
畅通工程 (最小生成树)
畅通工程 (最小生成树)
35 0
2021杭电多校第三场-Road Discount-wqs二分+最小生成树
get函数是求出将黑色的边权加上一个值x之后的一个花费,我们会这个函数处理出x=-1000->1000的所有情况,然后将信息储存在save中,然后在询问的时候,直接遍历save集合,遇见满足情况的便直接输出,否则输出-1,虽然没有-1的情况/doge
124 0
2021杭电多校第三场-Road Discount-wqs二分+最小生成树
|
测试技术
HDU-1232,畅通工程(并查集)
HDU-1232,畅通工程(并查集)
|
人工智能 算法
HDOJ2063过山车 匈牙利算法
HDOJ2063过山车 匈牙利算法
93 0
|
Java
HDOJ/HDU 5686 Problem B(斐波拉契+大数~)
HDOJ/HDU 5686 Problem B(斐波拉契+大数~)
84 0
HDOJ 1285 确定比赛名次(拓扑排序)
HDOJ 1285 确定比赛名次(拓扑排序)
123 0