HDOJ1233 畅通工程之一(最小生成树-Kruscal)

简介:

题目:

  1233 还是畅通工程
复制代码
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define M 101
 8 typedef struct{
 9     int x,y;
10     int len;
11 }EDGE;
12 
13 EDGE edge[M*M];
14 int Map[M][M];
15 int n,m;
16 int set[M];
17 
18 void ReadMap();
19 void InitSet();
20 int cmp(const EDGE &a,const EDGE &b);
21 int FindSet(int a);
22 void MergeSet(int a,int b);
23 void main()
24 {
25     int c,s,f,t;
26     while (scanf("%d",&n),n)
27     {
28         m = (n*(n-1))>>1;
29         ReadMap();
30         InitSet();
31         c = 0;//choosed node
32         s = 0;//sum length
33         sort(edge,edge+m,cmp);//sort the edges
34         for (int i=0;i<m && c!=n;i++)
35         {
36             f = FindSet(edge[i].x);
37             t = FindSet(edge[i].y);
38             if (f!=t)
39             {
40                 MergeSet(f,t);
41                 c++;
42                 s += edge[i].len;
43             }
44         }
45         cout<<s<<endl;
46 
47     }
48 }
49 void ReadMap()
50 {
51     for (int i=0;i<m;i++)
52         cin>>edge[i].x>>edge[i].y>>edge[i].len;
53 }
54 void InitSet()
55 {
56     for (int i=1;i<=n;i++)
57         set[i] = i;
58 }
59 int cmp(const EDGE &a,const EDGE &b)
60 {
61     return a.len<b.len;
62 }
63 int FindSet(int a)
64 {
65     return set[a];
66 }
67 void MergeSet(int a,int b)
68 {
69     for (int i=1;i<=n;i++)
70     {
71         if (set[i] == a)
72         {
73             set[i] = b;
74         }
75     }
76 }
复制代码

 


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

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