【codevs 1231】最优布线问题

2018-06-17 21:48:26来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述 Description

学校需要将n台计算机连接起来,不同的2台计算机之间的连接费用可能是不同的。为了节省费用,我们考虑采用间接数据传输结束,就是一台计算机可以间接地通过其他计算机实现和另外一台计算机连接。

为了使得任意两台计算机之间都是连通的(不管是直接还是间接的),需要在若干台计算机之间用网线直接连接,现在想使得总的连接费用最省,让你编程计算这个最小的费用。

输入描述 Input Description

输入第一行为两个整数n,m(2<=n<=100000,2<=m<=100000),表示计算机总数,和可以互相建立连接的连接个数。接下来m行,每行三个整数a,b,c 表示在机器a和机器b之间建立连接的话费是c。(题目保证一定存在可行的连通方案, 数据中可能存在权值不一样的重边,但是保证没有自环)

输出描述 Output Description

输出只有一行一个整数,表示最省的总连接费用。

样例输入 Sample Input

3 3

1 2 1

1 3 2

2 3 1

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

最终答案需要用long long类型来保存

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define maxn 100005
 6 using namespace std;
 7 int fa[maxn],deep[maxn];
 8 int n,m,tot=0;long long ans=0;
 9 struct node{int u,v,w;}e[maxn];
10 bool cmp(node a,node b){return a.w<b.w;}
11 int find(int x){
12     if(fa[x]==x) return x;
13     else return fa[x]=find(fa[x]);
14 }
15 void unite(int x,int y){
16     x=find(x),y=find(y);
17     if(x==y) return ;
18     if(deep[x]<deep[y]) fa[x]=y;
19     else{
20         fa[y]=x;
21         if(deep[x]==deep[y]) deep[y]++;
22     }
23 }
24 bool same(int a,int b){
25     return find(a)==find(b);
26 }
27 int main(){
28     scanf("%d%d",&n,&m);
29     for(int i=1;i<=n;i++) fa[i]=i,deep[i]=0;
30     for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
31     sort(e+1,e+m+1,cmp);
32     for(int i=1;i<=m;i++){
33         if(same(e[i].u,e[i].v)) continue;
34         else{
35             unite(e[i].u,e[i].v);
36             ans+=e[i].w;
37             tot++;
38         }
39     }
40     printf("%lld",ans);
41     return 0;
42 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【luogu 3865】【模板】ST表

下一篇:HDU_5538_House Building