专栏首页数据结构与算法1231 最优布线问题

1231 最优布线问题

1231 最优布线问题

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 白银 Silver

题目描述 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<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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P2782 友好城市

    题目背景 无 题目描述 有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城...

    attack
  • POJ 2104 K-th Number(主席树)

    Description You are working for Macrohard company in data structures department...

    attack
  • 洛谷P5245 【模板】多项式快速幂(多项式ln 多项式exp)

    attack
  • P2782 友好城市

    题目背景 无 题目描述 有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城...

    attack
  • HDU 3018 Ant Trip(欧拉回路)

    #include <bits/stdc++.h> using namespace std; const int N=100005; int f[N]; ...

    用户2965768
  • 最大连续子序列和(最大子数组和)四种最详细的解法

    解法1:穷举暴力法 枚举左端点跟右端点,然后遍历更新所有的子序列和,最终得到结果就是最大的

    杨鹏伟
  • 不引入新的数组,实现数组元素交换位置函数

             最近遇到一道C++的面试题,要求不引入新的数组,实现数组元素交换位置函数,看似挺简单的,却还是花费了我不少时间,这里记录下来,给大家一个简单的...

    用户1221057
  • POJ 2104 K-th Number(主席树)

    Description You are working for Macrohard company in data structures department...

    attack
  • 【2020HBU天梯赛训练】7-50 部落

    在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不...

    韩旭051
  • LeetCode 164. Maximum Gap (排序)

    题解:首先,当然我们可以用快排,排完序之后,遍历一遍数组,就能得到答案了。但是快速排序的效率是O(n* logn),不是题目要求的线性效率,也就是O(n)的效率...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券