最优布线难题

1231 最优布线难题

 

时限: 1 s

空间范围: 12七千 KB

标题等级 : 白银 Silver

 

 

 

 

题材叙述 Description

该校必要将n台总计机连接起来,分裂的2台微型总括机之间的连天费用或者是差异的。为了节省开销,大家考虑采用间接数据传输结束,正是一台微机能够直接地通过其余电脑完成和其它一台总计机连接。

为了使得任意两台总结机之间都以联网的(不管是直接大概直接的),要求在多少台微型总括机之间用网线直接连接,未来想使得总的连接开销最省,让您编制程序总结这么些小小的开销。

输入描述 Input Description

输入第3表现多少个整数n,m(2<=n<=一千00,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类型来保存

 

水题 裸卡路丝Carl

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=300001;
 7 struct node
 8 {
 9     int u;
10     int v;
11     int w;
12 }edge[MAXN];
13 int num=1;
14 int father[MAXN];
15 int comp(const node & a,const node & b)
16 {
17     if(a.w<b.w)return 1;
18     else return 0;
19 }
20 int find(int x)
21 {
22     if(father[x]!=x)
23     father[x]=find(father[x]);
24     return father[x];
25 }
26 void unionn(int x,int y)
27 {
28     int fx=find(x);
29     int fy=find(y);
30     father[fx]=fy;
31 }
32 int main()
33 {
34     int n,m;
35     scanf("%d%d",&n,&m);
36     for(int i=1;i<=n;i++)father[i]=i;
37     for(int i=1;i<=m;i++)
38     {
39         scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
40         num++;
41     }
42     sort(edge+1,edge+num,comp);
43     long long int k=0;
44     long long int tot=0;
45     for(int i=1;i<=num-1;i++)
46     {
47         if(find(edge[i].u)!=find(edge[i].v))
48         {
49             unionn(edge[i].u,edge[i].v);
50             tot=tot+edge[i].w;
51             k++;
52         }
53         if(k==n-1)break;
54     }
55     printf("%lld",tot);
56     return 0;
57 }

 

标题叙述 Description

全校供给将n台总结机连接起来,不一样的2台总括机之间的连接开销或许是见仁见智的。为了省去费用,大家着想动用直接数据传输停止,就是一台电脑能够直接地通过其余电脑达成和此外一台总括机连接。

为了使得任意两台计算机之间都以连接的(不管是直接或然直接的),供给在多少台总结机之间用网线直接连接,未来想使得总的连接开销最省,让您编制程序总结那么些非常的小的开支。

输入描述 Input Description

输入第1行事四个整数n,m(2<=n<=一千00,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 }