[C++][算法基础]求最小生成树(Kruskal)

给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。

求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible

给定一张边带权的无向图 G=(V,E),其中 V 表示图中点的集合,E 表示图中边的集合,n=|V|,m=|E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树,其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行,每行包含三个整数 u,v,w,表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式

共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible

数据范围

1≤n≤10^{5},
1≤m≤2∗10^{5},
图中涉及边的边权的绝对值均不超过 1000。

输入样例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例:
6

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 100010,M = 200010;
int n,m,x,y,z;
int res = 0;
int cnt = 0;
int p[N];

struct edge{
    int a,b,w;
}Edge[M];

bool CompareWith(edge A, edge B){
    if(A.w < B.w){
        return true;
    }else{
        return false;
    }
}

int Findroot(int x){
    if(p[x] != x){
        p[x] = Findroot(p[x]);
    }
    return p[x];
}

void Kruskal(){
    for(int i = 0;i < m;i++){
        int a = Edge[i].a;
        int b = Edge[i].b;
        int w = Edge[i].w;
        a = Findroot(a);
        b = Findroot(b);
        if(a != b){
            res += w;
            cnt++;
            p[a] = b;
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i = 0;i < m;i++){
        cin>>x>>y>>z;
        Edge[i] = {x,y,z};
    }
    sort(Edge,Edge + m,CompareWith);
    for(int i = 0;i < n;i++){
        p[i] = i;
    }
    Kruskal();
    if(cnt < n-1){
        cout<<"impossible"<<endl;
    }else{
        cout<<res<<endl;
    }
    return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/546918.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

民航电子数据库:[E14024]事务内变更操作次数超过最大许可值10000,可通过系统参数max_trans_modify适当调整限制

目录 一、场景二、异常情况三、原因四、排查五、解决 一、场景 1、对接民航电子数据 2、执行delete语句时报错 二、异常情况 三、原因 通过报错信息就可以看出&#xff0c;是系统参数max_trans_modify配置导致 当删除的数据量 > max_trans_modify时&#xff0c;删除就会…

Visual studio项目默认“Header Files”、“Source Files”等过滤器消失后展开的方法。

使用Visual Studio进行项目开发创建默认工程的解决方案资源管理器里查看项目文件&#xff0c;所有的文件是按照其所属的类型自动归类&#xff0c;例如&#xff1a;.h头文件自动划归到Header Files文件夹&#xff0c;.cpp文件自动划归到Source Files文件夹下&#xff0c;如下图所…

关于AG32 MCU的一些奇思妙想

1、AG32VF103的网口是100M还是10M&#xff1f; RE: 都是100M的。 2、用FPGA能不能再仿出一个网口&#xff1f;有些产品用到两个网口。 理论上可以&#xff0c;但是要考虑&#xff0c;一个是cpld实现难度&#xff0c;一个是需要的逻辑单元。因为mac逻辑多&#xff0c;内置的2KL…

Python Flask Web 框架-API接口开发_4

一、1、安装 Falsk 当前用户安装 pip3 install --user Flask 确认安装成功&#xff1a; 进入python交互模式看下Flask的介绍和版本&#xff1a; $ python3>>> import flask >>> print(flask.__doc__)flask~~~~~A microframework based on Werkzeug. Its …

快速掌握Spring监控(Spring Boot admin)

监控 监控可视化监控平台Admin底层逻辑info 自定义端点 监控 监控的作用&#xff1a; 监控服务状态是否宕机监控服务运行指标&#xff08;内存&#xff0c;虚拟机&#xff0c;线程&#xff0c;请求等&#xff09;监控日志管理服务&#xff08;服务下线&#xff09; 监控的实…

linux进阶篇:使用Apache搭建文件服务器目录

Linux服务搭建篇&#xff1a;使用Apache搭建文件服务器目录 一、关于文件服务器 ​ 在一个项目中&#xff0c;如果想把公共软件或者资料共享给项目组成员&#xff0c;可以搭建一个简易的文件服务器来实现&#xff0c;只要是在局域网内的成员都可以通过浏览器或者wget命令来下…

书生·浦语大模型全链路开源体系-第5课

书生浦语大模型全链路开源体系-第5课 书生浦语大模型全链路开源体系-第5课相关资源LMDeploy基础配置LMDeploy运行环境下载internlm2-chat-1_8b模型使用Transformer来直接运行InternLM2-Chat-1.8B模型使用LMDeploy以命令行方式与InternLM2-Chat-1.8B模型对话设置KV Cache最大占用…

wps使用Latex编辑公式没有Latex formula

wps使用Latex编辑公式没有Latex formula 1. 下载CTEX2. 下载LaTeXEE3. 配置Miktex4. 配置latexee5. 用管理员权限运行latexeqedit.exe6. wps插入latex公式 1. 下载CTEX 下载CTEX网址&#xff0c;我下载的下图这个&#xff0c;下载完了之后运行exe文件安装ctex。 2. 下载LaTe…

视频国标学习

总体介绍 GB/T28181协议&#xff0c;全名叫《安全防范视频监控联网系统信息传输、交换、控制技术要求》&#xff0c;是由中国国家标准委员会发布的一种国家级的标准。它主要对视频监控系统的各个方面做了明确的规定&#xff0c;使得不同厂商生产的视频监控设备能够相互连通&am…

【C++】<入门>C++入门基础知识

C入门 1. 入门0. 本节知识点熟悉目的1. C关键字&#xff08;C98&#xff09; 2. 命名空间2.1 命名空间定义2.2 命名空间使用 3. C输入&输出4. 缺省参数4.1 缺省参数概念4.2 缺省参数分类 5. 函数重载5.1 函数重载概念5.2 C支持函数重载的原理--名字修饰&#xff08;name Ma…

IntelliJ IDEA 2023中文--让编程更高效、更智能

IntelliJ IDEA 2023是一款功能强大的集成开发环境&#xff08;IDE&#xff09;&#xff0c;专为Java开发者打造。它以其智能、高效和人性化的特点&#xff0c;帮助开发者更快、更好地编写代码。IntelliJ IDEA 2023支持多种语言和框架&#xff0c;包括Java、Kotlin、Spring等&am…

SpringCloud之LoadBalancer负载均衡器的简单使用

SpringCloud之LoadBalancer负载均衡器的简单使用 loadbalancer用于对提供服务的集群做一个节点的选取规则。 如图所示&#xff0c;load balancer集成在调用方 示例 创建loadbalance-base模块,并引入相关依赖 <dependencies><dependency><groupId>org.spr…

Unity笔记之下拉刷新列表

这样的效果&#xff1b; 代码&#xff1a; using System; using System.Collections; using System.Collections.Generic; using Sirenix.OdinInspector; using UnityEngine; using UnityEngine.EventSystems; using UnityEngine.UI;public class ScrollRectUpdateView : Mon…

解锁创意无限,体验全新Adobe Illustrator 2021 for mac/Win中文版

在数字化创意的浪潮中&#xff0c;Adobe Illustrator 2021中文版无疑是设计师们的得力助手。这款软件集高效、便捷、创新于一体&#xff0c;无论是Mac还是Windows用户&#xff0c;都能在其中找到属于自己的创意空间。 Adobe Illustrator 2021中文版延续了其强大的矢量图形处理…

5.2 mybatis之autoMappingBehavior作用

文章目录 1. NONE关闭自动映射2. PARTIAL非嵌套结果映射3. FULL全自动映射 众所周知mybatis中标签< resultMap >是用来处理数据库库字段与java对象属性映射的。通常java对象属性&#xff08;驼峰格式&#xff09;与数据库表字段&#xff08;下划线形式&#xff09;是一 一…

万界星空科技商业开源MES+项目合作+低代码平台

今天我想和大家分享的是一套商业开源的 MES制造执行管理系统。对于制造业而言&#xff0c;MES 是一个至关重要的系统&#xff0c;它可以帮助企业提高生产效率、优化资源利用、提高产品质量&#xff0c;从而增强市场竞争力。什么是 MES&#xff1f; MES 是指通过计算机技术、自动…

【数据库】表的增删改(CUD)

目录 一、insert 插入 1.单行插入&#xff1a; 2.多行插入&#xff1a; (1) insert into 插入&#xff1a; (2) replace into 替换插入&#xff1a; (3) 图片插入 &#xff1a; 二、update 修改 三、delete 删除 一、insert 插入 语法&#xff1a; INSERT INTO table_name…

尚硅谷html5+css3(4)浮动

1.浮动的概念 <head><style>.box1 {width: 200px;height: 200px;background-color: orange;/*通过浮动可以使一个元素向其父元素的左侧或右侧移动使用float属性设置子资源的浮动可选值&#xff1a;none默认值&#xff0c;元素不浮动left向左浮动right向右浮动注意…

VSCode中vue的packag.json报错:unable to load schema from‘ http://json.schema‘...问题解决

package.json有这个报错&#xff0c;类似于这种问题一般是网络连接有问题&#xff0c;无法加载重启一下就好。 但是如果是没有网络或者云桌面等环境不能连接外网&#xff0c;就在设置中把这个设置一下&#xff0c;这样就不报错了&#xff0c;根据需要选择处理。

系统开发实训小组作业week7 —— 优化系统开发计划

目录 1. 建立规则&#xff0c;仪式&#xff0c;流程&#xff0c;模式 2. 给好行为正面的反馈 3. 明确指出不合适的行为&#xff0c;必要时调整人员 在 “系统开发实训课程” 中&#xff0c;我们小组的项目是 “电影院会员管理系统” 。在项目的开发过程中&#xff0c;我们遇…