P3366 【模板】最小生成树

题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出orz

输入输出格式

输入格式:

第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N<=5000,M<=200000)

接下来M行每行包含三个整数Xi、Yi、Zi,表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式:

输出包含一个数,即最小生成树的各边的长度之和;如果该图不连通则输出orz

输入输出样例

输入样例#1:

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出样例#1:

7

说明

时空限制:1000ms,128M

数据规模:

对于20%的数据:N<=5,M<=20

对于40%的数据:N<=50,M<=2500

对于70%的数据:N<=500,M<=10000

对于100%的数据:N<=5000,M<=200000

样例解释:

所以最小生成树的总边权为2+2+3=7

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

【问底】王帅:深入PHP内核(一)——弱类型变量原理探究

PHP是一门简单而强大的语言,提供了很多Web适用的语言特性,其中就包括了变量弱类型,在弱类型机制下,你能够给一个变量赋任意类型的值。 PHP的执行...

31150
来自专栏代码世界

Python之面向对象三

面向对象的三大特性: 多态 多态指的是一类事物有多种形态。Python3天生支持多态。 动物有多种形态:人,狗,猪 import abc class Anima...

376100
来自专栏程序员的诗和远方

谈谈 JavaScript 中的 TDZ

本来过年期间想写这个的,不过要准备些东西,一直没抽出时间,刚好今天有点空闲。上个月阮一峰阮老师在微博上发布了这样一条信息 于是评论区炸开了锅,很多人留言指出,这...

34470
来自专栏小樱的经验随笔

April Fools Contest 2017 题解&源码(A,数学 B,数学 C,数学 D,字符串 E,数字逻辑 F,排序,卡时间,G,数学)

A. Numbers Joke time limit per test:2 seconds memory limit per test:64 megabytes...

36750
来自专栏CSDN技术头条

【问底】静行:FastJSON实现详解

还记得电影《功夫》中火云邪神的一句话:天下功夫,无坚不破,唯快不破。在程序员的世界中,“快”一直是大家苦苦修炼,竞相追逐的终极目标之一,甚至到了“不择手段”、“...

31370
来自专栏刘望舒

JNI的实现原理

JNI是Java Native Interface的缩写,它为java提供了调用C和C++代码的能力。java.lang包下的很多类都用到了native方法,比...

59420
来自专栏xiaoxi666的专栏

状态机编程思想(2):删除代码注释(目前支持C/C++和Java)

之前考虑过正则表达式,但是感觉实现起来相当麻烦。而状态机可以把多种情况归为一类状态再行分解,大大简化问题。本文就是基于状态机实现的。

14220
来自专栏雪胖纸的玩蛇日常

第二章 基本数据结构

21280
来自专栏SeanCheney的专栏

Python解答LeetCode

古有科举八股,今有LeetCode。 八股定格式而取文采心意,LeetCode定题目且重答案背诵。 美其名曰:"practice makes perfec...

799160
来自专栏偏前端工程师的驿站

(cljs/run-at (JSVM. :all) "一次说白DataType、Record和Protocol")

前言  在项目中我们一般会为实际问题域定义领域数据模型,譬如开发VDOM时自然而言就会定义个VNode数据类型,用于打包存储、操作相关数据。clj/cljs不单...

20080

扫码关注云+社区

领取腾讯云代金券