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

给定一个 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≤500,
1≤m≤10^{5},
图中涉及边的边权的绝对值均不超过 10000。

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

代码:

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

const int N = 510;
int G[N][N];
int dist[N];
int att[N];
int n,m,x,y,z;

int Prim(){
    int res = 0;
    memset(dist,0x3f,sizeof dist);
    for(int i = 0;i < n;i++){
        int t = -1;
        for(int j = 1;j <= n;j++){
            if(att[j] == 0 && (t == -1||dist[j] < dist[t])){
                t = j;
            }
        }
        if(i != 0 && dist[t] == 0x3f3f3f3f){
            return 0x3f3f3f3f;
        }
        if(i != 0){
            res += dist[t];
        }
        att[t] = 1;
        for(int j = 1;j <= n;j++){
            dist[j] = min(dist[j], G[t][j]);
        }
    }
    return res;
}

int main(){
    cin>>n>>m;
    
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(i == j){
                G[i][j] = 0;
            }else{
                G[i][j] = 0x3f3f3f3f;
            }
        }
    }
    while(m--){
        cin>>x>>y>>z;
        G[x][y] = min(G[x][y], z);
        G[y][x] = min(G[y][x], z);
    }
    int ans = Prim();
    if(ans > 0x3f3f3f3f / 2){
        cout<<"impossible"<<endl;
    }else{
        cout<<ans<<endl;
    }
    return 0;
}

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

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

相关文章

【C++】explicit关键字详解(explicit关键字是什么? 为什么需要explicit关键字? 如何使用explicit 关键字)

目录 一、前言 二、explicit关键字是什么&#xff1f; 三、构造函数还具有类型转换的作用 &#x1f34e;单参构造函数 ✨引出 explicit 关键字 &#x1f34d;多参构造函数 ✨为什么需要explicit关键字&#xff1f; ✨怎么使用explicit关键字&#xff1f; 四、总结 五…

硕博电子经济型高性能LED面板

在科技进步的洪流中&#xff0c;硕博电子始终保持敏锐的洞察力与创新能力。SPM-LEDP-C12是硕博电子开发的兼具性价比与创新性能的LED面板。该产品具备1路CAN总线&#xff0c;12个LED指示灯&#xff08;丝印字符带背光&#xff09;。 不同于以往独立控制的单个指示灯&#xff…

StableDiffusion-02 LoRA上手使用实测 尝试生成图片 使用多个LoRA 调整LoRA效果 10分钟上手 多图

准备工作 请你确保&#xff0c;你已经完成了 StableDiffusion-01 这一节的内容&#xff0c;可以顺利的运行SD&#xff0c;并且可以正常的生成图片。 本节我们就尝试使用LoRA并生成图片。 介绍 LoRA Stable Diffusion中的LoRA&#xff08;Low-Rank Adaptation&#xff0c;低秩…

ubuntu下的串口调试工具cutecom

系统&#xff1a;ubuntu20.04 &#xff08;1&#xff09;接线 使用 rs485&#xff1c;-----> rs232 转接口&#xff08; 设备直接出来的是rs485&#xff09;&#xff0c;电脑主机接入一根 rs232&#xff1c;-----> USB口 连接线&#xff0c;ubuntu系统下打开 termin…

【Vue】setup语法糖的使用

文章目录 setup简介使用vite-plugin-vue-setup-extend插件 指定组件名字 setup简介 <script setup> 是在单文件组件 (SFC) 中使用组合式 API 的编译时语法糖 相比较普通的<script> ,它有以下优势&#xff1a; 更少的样板内容&#xff0c;更简洁的代码。能够使用纯…

RocketMQ为什么这么快?

如果你对 RocketMQ 还不了解&#xff0c;可以查看我之前写的关于 RocketMQ 专栏 的几篇文章 如果你对 RocketMQ 源码也感兴趣&#xff0c;可以从下面这个仓库 fork 一下源码&#xff0c;我在源码中加了中文注释&#xff0c;并且后面我还会持续更新注释 https://github.com/san…

自然语言处理——情绪检测数据集

一、重要性及意义 情绪检测的重要性和意义体现在多个方面&#xff0c;不仅对于个人日常生活有深远影响&#xff0c;也在多个行业和领域中扮演着关键角色。以下是情绪检测的重要性和意义的具体体现&#xff1a; 提高人机交互体验&#xff1a; 在人工智能和机器学习驱动的系统中…

MySQL慢SQL优化方案汇总

⛰️个人主页: 蒾酒 &#x1f525;系列专栏&#xff1a;《mysql经验总结》 &#x1f30a;山高路远&#xff0c;行路漫漫&#xff0c;终有归途 目录 写在前面 优化思路 避免查询不必要的列 分页优化 索引优化 JOIN优化 排序优化 UNION 优化 写在最后 写在前面 本…

Netty学习——实战篇3 BIO与NIO零拷贝 和 Netty入门实战

1 BIO拷贝 BIOServer.java public class BIOServer {public static void main(String[] args) throws Exception{ServerSocket serverSocket new ServerSocket(8000);while(true){Socket socket serverSocket.accept();DataInputStream inputStream new DataInputStream(so…

使用美化方法设计嵌入的子窗体(三)

使用美化方法设计嵌入的子窗体 分析效果图的实现 效果图&#xff1a; 新建 Windows 窗体 新窗体命名&#xff1a;FrmAddProduct.cs修改窗体的 Text 属性&#xff1a;新增商品修改窗体的位置&#xff1a;StartPosition&#xff1a;CenterScreen窗体的无边框设计&#xff1a…

拼多多容器文件修改自动上传

拼多多开放平台php环境是官方的linux容器&#xff0c;不能自己搭建ftp上传文件&#xff0c;每每有文件更新都挺麻烦。 有些功能测试不想每次都打包全部代码上去重新发布一次程序生成新的容器&#xff0c;那样太过麻烦和效率低。 一开始搞了一个php的文件管理工具上去&#xf…

电压比较器LM339介绍和仿真

电压比较器LM339介绍和仿真 &#x1f4d1;LM339相关特性 工作电源电压范围宽&#xff0c;单电源、双电源均可工作&#xff0c;单电源&#xff1a; 2&#xff5e;36V&#xff0c;双电源&#xff1a;1&#xff5e;18V&#xff1b;消耗电流小&#xff0c; Icc1.3mA&#xff1b;输…

《Kubernets证书篇:基于Kylin V10+ARM架构CPU修改K8S 1.26.15版本证书时间限制》

一、背景 Kubernetes 默认的证书有效期只有1年&#xff0c;因此需要每年手动更新一次节点上面的证书&#xff0c;特别麻烦而且更新过程中可能会出现问题&#xff0c;因此我们要对 Kubernetes 的 SSL 证书有效期进行修改&#xff0c;这里将证书的时间限制修改为100年。 环境信息…

【日常记录】【JS】styled-components库的原理,模板字符串调用函数

文章目录 1、引言2、模板字符串调用函数3、实现 1、引言 在react 中&#xff0c;styled-components 是最流行的 css in js 模式的库 2、模板字符串调用函数 let stu {name: 呆呆狗,age: 30,address: 中国}let str fn你好${stu.name}今年${stu.age}岁,来自${stu.address}这样会…

MySql 安装,小白也可以学会成功安装的保姆级教程

MySql 安装 文章目录 MySql 安装1.Mysql下载1.1 访问下载链接1.2 选择合适版本1.3 下载安装包 2.MySql安装3.安装成功检测验证3.1 mysql自带控制台验证3.2 win系统控制台进入验证 4. mysql 配置path5. navicat 连接 mysql 1.Mysql下载 1.1 访问下载链接 MySQL Downloads 这里…

计算机网络----第十六天

OSPF基础 RIP的缺陷&#xff1a; 最大16跳不可达&#xff1b; 收敛速度慢&#xff1b; 协议会产生路由自环 每发一次路由更新&#xff0c;就将自己的全部路由信息发送出去&#xff1b; OSPF&#xff1a; 含义&#xff1a;ospf&#xff08;最短路径优先&#xff09;&…

【Github】一个用于Active Directory的自助密码更改工具

在众多企业的日常运营中&#xff0c;Active Directory&#xff08;AD&#xff09;扮演着核心角色&#xff0c;负责管理和维护员工账户。然而&#xff0c;密码重置作为IT支持团队的常规工作之一&#xff0c;往往既耗时又繁琐。虽然一些商业解决方案和通过Windows服务器上RDS服务…

航芯通用MCU技术常见问题 | F4专题

日常工作中&#xff0c;我们的销售或技术工程师经常会收到来自用户的问题&#xff0c;其中一些问题是比较常见的&#xff0c;所以为满足日常用户对航芯产品使用及服务的了解&#xff0c;航芯特此推出“通用MCU技术常见问题”专题&#xff0c;分为F0专题及F4专题&#xff0c;欢迎…

内网穿透是什么意思?快解析如何实现内网穿透

在家里或者公司&#xff0c;我们常常会使用路由器来连接网络&#xff0c;以便我们能够上网学习和工作&#xff0c;但有时候使用起来真的不方便。有的时候我们在外面&#xff0c;想访问家里或者公司内部的设备&#xff0c;就会碰到一个问题&#xff1a;我们无法直接通过公网IP访…

【LeetCode: 3117. 划分数组得到最小的值之和 + 动态规划】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…