力扣--图论/Prim1584.连接所有点的最小费用

思路分析:

  1. 初始化:获取点的数量,并创建两个辅助数组 adjvexlowcost,分别用于记录最小生成树的边信息和每个顶点到最小生成树的距离。
  2. Prim算法循环:在每一次循环中,选择一个未加入最小生成树的顶点 k,使得从已加入最小生成树的顶点到 k 的距离最小。循环 n-1 次,每次选择一个顶点加入最小生成树。
  3. 找出下一个顶点:遍历所有未加入最小生成树的顶点,选择距离最小的顶点 k,加入最小生成树,并标记顶点 k 已被访问。
  4. 更新最小生成树信息:更新 lowcost 数组,更新每个顶点到最小生成树的距离。
  5. 计算总成本:计算最小生成树的总成本,即所有边的长度之和,并返回。
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(); // 获取点的数量

        // 用于存储最小生成树的边信息
        vector<int> adjvex(n, 0); // 记录最小生成树的顶点的下标
        vector<int> lowcost(n, 0); // 记录从最小生成树中的某顶点到其它顶点的最小权值

        // 初始化lowcost数组,将除了第一个点以外的顶点到第一个点的距离记录下来
        for(int i = 1; i < n; i++)
            lowcost[i] = abs(points[i][0] - points[0][0]) + abs(points[i][1] - points[0][1]);

        // 用于记录顶点是否已被访问过
        vector<bool> visited(n, false);

        // Prim算法的主要循环,构建最小生成树
        for(int t = 0; t < n - 1; t++) {
            int k = 1, min = INT_MAX;
            // 找出lowcost数组中的最小值
            for(int i = 1; i < n; i++) {
                if(lowcost[i] < min && visited[i] == false) {
                    min = lowcost[i];
                    k = i;
                }
            }
            // 标记顶点k已被访问
            visited[k] = true;
            // 将k顶点到其它顶点的权值设为0,表示已加入最小生成树
            lowcost[k] = 0;
            // 更新lowcost数组中的值
            for(int i = 1; i < n; i++) {
                if(i != k) {
                    // 计算顶点i到顶点k的距离
                    int close = abs(points[i][0] - points[k][0]) + abs(points[i][1] - points[k][1]);
                    // 如果顶点i到顶点k的距离小于当前到顶点i的最小权值,则更新相应信息
                    if(lowcost[i] > close) {
                        adjvex[i] = k;
                        lowcost[i] = close;
                    }
                }
            }
        }

        // 计算最小生成树的总成本
        int num = 0;
        for(int i = 0; i < n; i++) {
            num += abs(points[i][0] - points[adjvex[i]][0]) + abs(points[i][1] - points[adjvex[i]][1]);
        }
        // 返回最小生成树的总成本
        return num;
    }
};

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

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

相关文章

登陆qq,经常收到qq游戏中心的推送信息,关闭推送信息

手动关闭推送信息的步骤&#xff1a; 1.点开左侧游戏中心 2、在打开界面&#xff0c;点击左下角自己的头像 3、打开设置中心&#xff0c;关闭所有的推送 4、完成关闭&#xff0c;不会推送了

使用 Prometheus 在 KubeSphere 上监控 KubeEdge 边缘节点(Jetson) CPU、GPU 状态

作者&#xff1a;朱亚光&#xff0c;之江实验室工程师&#xff0c;云原生/开源爱好者。 KubeSphere 边缘节点的可观测性 在边缘计算场景下&#xff0c;KubeSphere 基于 KubeEdge 实现应用与工作负载在云端与边缘节点的统一分发与管理&#xff0c;解决在海量边、端设备上完成应…

基于SSM+Jsp+Mysql的旅游网站设计与实现

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

数据链路层(上):以太网、二层交换机和网络风暴

目录 数据链路层知识概览 数据链路层设备 1、二层交换机 2、拓展&#xff1a;二层交换机与三层交换机有啥区别&#xff1f; 3、广播风暴 4、交换机以太网接口的工作模式 数据链路层的功能 数据链路层--以太网 1、以太网是什么&#xff1f; 2、以太网地址 数据链路层知…

手把手教你安装深度学习框架PyTorch:一键式安装指南

随着人工智能和深度学习的飞速发展&#xff0c;PyTorch作为一个强大而灵活的深度学习框架&#xff0c;受到了越来越多研究者和开发者的青睐。PyTorch不仅易于上手&#xff0c;而且支持动态计算图&#xff0c;使得调试和实验变得非常方便。本文将手把手教你如何安装PyTorch&…

端口协议(爆破、未授权)

常见端口服务及攻击方向&#xff1a; 弱口令爆破 工具&#xff1a;https://github.com/vanhauser-thc/thc-hydra hydra是一个支持多协议的自动化的爆破工具。 支持的服务、协议&#xff1a; telnet ftp pop3[-ntlm] imap[-ntlm] smb smbnt http-{head|get} http-{get|post}-…

Flutter第八弹 构建拥有不同项的列表

目标&#xff1a;1&#xff09;项目中&#xff0c;数据源可能涉及不同的模版&#xff0c;显示不同类型的子项&#xff0c;类似RecycleView的itemType, 有多种类型&#xff0c;列表怎么显示&#xff1f; 2&#xff09;不同的数据源构建列表 一、创建不同的数据源 采用类似Rec…

直播弹幕系统设计

本文仅提供思路参考&#xff0c;并非完备的详细设计。 特点 其实很类似IM即时通讯系统&#xff0c;是个变种&#xff0c;本质也是在一个空间内收发消息 消息及时性强&#xff0c;过期消息意义不大用户松散&#xff0c;随时来随时走可能有瞬时大批量弹幕&#xff08;比如比赛精…

漫途水产养殖水质智能监测方案,科技助力养殖业高效生产!

随着水产养殖业的蓬勃发展&#xff0c;水质和饲料等多重因素逐渐成为影响其持续健康发展的关键因素。由于传统养殖模式因监控和调节手段不足&#xff0c;往往造成养殖环境的恶化。需要通过智能化养殖&#xff0c;调控养殖环境&#xff0c;实现养殖的精细化管理模式&#xff0c;…

【Git教程】(九)版本标签 —— 创建、查看标签,标签的散列值,将标签添加到日志输出中,判断标签是否包含特定的提交 ~

Git教程 版本标签&#xff08;tag&#xff09; 1️⃣ 创建标签2️⃣ 查看存在的标签3️⃣ 标签的散列值4️⃣ 将标签添加到日志输出中5️⃣ 判断tag是否包含特定的提交&#x1f33e; 总结 大多数项目都是用 1.7.3.2和 “ gingerbread” 这样的数字或名称来标识软件版本的。在 …

《由浅入深学习SAP财务》:第2章 总账模块 - 2.6 定期处理 - 2.6.6 年初操作:科目余额结转

2.6.6 年初操作&#xff1a;科目余额结转 在使用事务代码 FAGLB03 查询科目余额时&#xff0c;可以看到按期间的发生额清单。其中&#xff0c;第一行称为“余额结转”&#xff0c;该行的累计余额代表上年度遗留下来的余额&#xff0c;也就是年初余额。对于资产负债表科目而言&a…

中华人民共和国密码行业标准-各类标准文档下载

国家密码管理局 中华人民共和国密码行业标准 GmSSL Project 密码行业标准化技术委员会公布了所有密码行业标准&#xff0c;并支持全文查看&#xff0c;参见密码行业标准列表 GM/T 0001-2012 祖冲之序列密码算法 GM/T 0002-2012 SM4分组密码算法(原SMS4分组密码算法) GM/…

深度剖析整型和浮点型数据在内存中的存储(C语言)

目录 整型在内存中的存储 为什么整型在内存中存储的是补码&#xff1f; 大小端字节序 为什么有大端小端&#xff1f; 浮点型家族 浮点数在内存中的存储 long long 整型在内存中的存储 整型在内存中有三种二进制表示形式&#xff1a;原码&#xff0c;反码&#xff0c;补码…

Tomcat源码解析——Tomcat的启动流程

一、启动脚本 当我们在服务启动Tomcat时&#xff0c;都是通过执行startup.sh脚本启动。 在Tomcat的启动脚本startup.sh中&#xff0c;最终会去执行catalina.sh脚本&#xff0c;传递的参数是start。 在catalina.sh脚本中&#xff0c;前面是环境判断和初始化参数&#xff0c;最终…

Linux三剑客-sed、awk、egrep(上)

一、知识梗概 二、正则表达式 定义&#xff1a;正则表达式是一种强大的文本处理工具&#xff0c;用于在文本中搜索符合特定模式的字符串。它由一系列特殊字符和普通字符组成&#xff0c;可以定义复杂的搜索模式。正则表达式被广泛应用于各种编程语言和文本处理工具中。 简单来…

(2024,自回归,下一尺度预测,VQGAN)视觉自回归建模:通过下一尺度预测的可扩展的图像生成

Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Prediction 公和众和号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 3. 方法 3.1 基础&#xff1a;通过下…

OpenAI反超Claude3,GPT4.5-Turbo正式版发布,AI王座再次易主

没想到&#xff0c;仅仅过了两个月&#xff0c;全球最强AI的宝座又易主了&#xff01; 几个月前&#xff0c;Claude3 Opus全面超越GPT-4&#xff0c;全球的网友纷纷抛弃GPT&#xff0c;投向Claude3的怀抱&#xff0c;并纷纷分享Claude3带来的惊艳体验。 如今&#xff0c;Open…

Win10 使用Telnet

命令行 telnet 127.0.0.1 80 调试是否能连接服务 输入exit 回车即可退出 相比于ping的不同

k8s:kubectl 命令设置简写启用自动补全功能

k8s&#xff1a;kubectl 命令设置简写&启用自动补全功能 1、设置kubectl命令简写2、启用kubectl自动补全功能 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; Kubernetes&#xff08;K8s&#xff09;是一个强大的容器编排平台&#xff0…

生活中的数学 --- 等额本息贷款和等额本金贷款的月供应该怎么算?

等额本息贷款和等额本金贷款的月供应该怎么算&#xff1f; 从一个例子开始&#xff0c;假设我要从银行贷款36万(即&#xff0c;本金)&#xff0c;银行给出的贷款年利率是12%(月利率为年利率除以12)&#xff0c;贷款半年(6个月)&#xff0c;按月还款&#xff0c;分6期还完。 问分…