首页 > 代码库 > hdu 1233 还是畅通工程(最小生成树)
hdu 1233 还是畅通工程(最小生成树)
Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
当N为0时,输入结束,该用例不被处理。
Output
对每个测试用例,在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
思路:最小生成树,没什么好说的。 注意:因为输入量较多,所以用cin输入会超时,改用scanf输入。
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<stdlib.h> 5 #include<math.h> 6 #include<algorithm> 7 #define LL long long 8 #define mod 1e9 + 7 9 const int M = 105;10 11 using namespace std;12 13 struct node{14 int x;15 int y;16 int value;17 }a[M * M >> 1];18 19 int cun[M];20 21 22 bool cmp(node a, node b)23 {24 return a.value < b.value;25 }26 27 int find(int x)28 {29 return cun[x] == x ? x : cun[x] = find(cun[x]);30 }31 32 void shu(int x, int y)33 {34 int p = find(x);35 int q = find(y);36 cun[p] = q;37 }38 39 int main()40 {41 int n;42 while( cin >> n , n )43 {44 int t = n * (n - 1) / 2;45 for(int i = 0; i < t; ++i)46 scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].value);47 for(int i = 0; i <= n; ++i)48 cun[i] = i;49 sort(a,a + t,cmp);50 int ans = 0;51 for(int i = 0; i < t; ++i)52 {53 if(find(a[i].x) != find(a[i].y))54 {55 shu(a[i].x,a[i].y);56 ans += a[i].value;57 }58 }59 cout << ans << endl;60 }61 return 0;62 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。