T1231 最优布线 codevs
2024-09-04 09:20:28
http://codevs.cn/problem/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类型来保存
#include <algorithm>
#include <iostream>
#include <cstdio>
#define maxn 100001 using namespace std; typedef long long LL;
int n,m,a,b,c,tot,num=;
LL ans=;
int fa[maxn];
struct node
{
int u,v,w;
}e[maxn]; void add(int x,int y,int z)
{
tot++;
e[tot].u=x;
e[tot].v=y;
e[tot].w=z;
} int find(int x)
{
if(x!=fa[x])
fa[x]=find(fa[x]);
return x;
} bool cmp(node aa,node bb)
{
return aa.w<bb.w;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
sort(e+,e+tot+,cmp);
for(int i=;i<=tot;i++)
{
int xx=find(e[i].u),yy=find(e[i].v);
if(xx!=yy)
{
fa[yy]=xx;
num++;
ans+=e[i].w;
if(num==n-)
break;
} }
printf("%lld",ans);
return ;
}
最新文章
- 百度编辑器UEditor与UEditor 公式插件完整Demo
- HTML标签界里不会再用到的标签属性(一)
- jqGrid 操作一些总结
- Repeater用法
- NYOJ 16 矩形嵌套(经典动态规划)
- iOS苹果开发者客服电话地址
- C++文件操作之 seekg/seekp/tellg/tellp
- typedef用法小结
- php DOMDocument 递归 格式化缩进HTML文档
- poj - 1170 - Shopping Offers(减少国家dp)
- Jenkins获取git tags代码
- R语言︱词典型情感分析文本操作技巧汇总(打标签、词典与数据匹配等)
- Django web框架-----win10搭建django2.1.7开发环境,定义简易视图及网址
- LOJ-10096(强连通+bfs)
- Linux系统诊断必备技能之一:lsof 用法详解!
- JavaScript获取DOM节点
- [Hinton] Neural Networks for Machine Learning - Converage
- react-native 搭建环境
- 【转】python3实现自动化框架robotframework
- python 之模块之 xml.dom.minidom解析xml