Day57--图论--53. 寻宝(卡码网)

Day57–图论–53. 寻宝(卡码网)

今天学习:最小生成树。有两种算法(Prim和Kruskal)和一道例题。

prim 算法是维护节点的集合,而 Kruskal 是维护边的集合

最小生成树:所有节点的最小连通子图,即:以最小的成本(边的权值)将图中所有节点连接到一起。

53. 寻宝(卡码网)

方法:Prim最小生成树

思路:

  1. 第一步,选距离生成树最近节点
  2. 第二步,最近节点加入生成树
  3. 第三步,更新非生成树节点到生成树的距离(即更新minDist数组)(minDist数组用来记录每一个节点距离最小生成树的最近距离。)
import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int v = in.nextInt();int e = in.nextInt();int[][] grid = new int[v + 1][v + 1];for (int i = 0; i <= v; i++) {Arrays.fill(grid[i], 10001);}for (int i = 0; i < e; i++) {int from = in.nextInt();int to = in.nextInt();int val = in.nextInt();grid[from][to] = val;grid[to][from] = val;}int[] minDist = new int[v + 1];Arrays.fill(minDist, 10001);boolean[] isInTree = new boolean[v + 1];for (int i = 1; i < v; i++) {int cur = -1;int minVal = Integer.MAX_VALUE;for (int j = 1; j <= v; j++) {if (!isInTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}isInTree[cur] = true;for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}int sum = 0;for (int i = 2; i <= v; i++) {sum += minDist[i];}System.out.println(sum);}
}

方法:Kruskal最小生成树

思路:

  • 边的权值排序,因为要优先选最小的边加入到生成树里
  • 遍历排序后的边
    • 如果边首尾的两个节点在同一个集合,说明如果连上这条边图中会出现环
    • 如果边首尾的两个节点不在同一个集合,加入到最小生成树,并把两个节点加入同一个集合
import java.util.*;class Disjoint {private int[] father;public Disjoint(int n) {father = new int[n + 1];for (int i = 0; i <= n; i++) {father[i] = i;}}public int find(int a) {if (a == father[a]) {return a;} else {return father[a] = find(father[a]);}}public boolean isSame(int o1, int o2) {return find(o1) == find(o2);}public void join(int o1, int o2) {int root1 = find(o1);int root2 = find(o2);if (root1 == root2) {return;}father[root2] = root1;}
}public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int v = in.nextInt();int e = in.nextInt();Disjoint dj = new Disjoint(v);int[][] edges = new int[e][3];for (int i = 0; i < e; i++) {edges[i][0] = in.nextInt();edges[i][1] = in.nextInt();edges[i][2] = in.nextInt();}Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));int sum = 0;for (int i = 0; i < e; i++) {int n1 = edges[i][0];int n2 = edges[i][1];int val = edges[i][2];if (!dj.isSame(n1, n2)) {dj.join(n1, n2);sum += val;}}System.out.println(sum);}
}

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

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

解决海洋探测数据同步网络问题的新思路——基于智能组网技术的探索

随着海洋探测技术的不断发展&#xff0c;数据同步网络的稳定性和低延迟需求变得愈发重要。海洋探测数据来自多个分布式采集点&#xff0c;这些点需要高效的组网方式来实现实时数据传输。然而&#xff0c;由于海洋环境的特殊性&#xff08;如复杂的网络拓扑、高湿度和极端温度&a…

设计模式笔记_行为型_责任链模式

1. 责任链模式介绍责任链模式&#xff08;Chain of Responsibility&#xff09;是一种行为设计模式&#xff0c;它允许将多个处理器&#xff08;处理对象&#xff09;连接成一条链&#xff0c;并沿着这条链传递请求&#xff0c;直到有一个处理器处理它为止。职责链模式的主要目…

pygame的帧处理中,涉及键盘的有`pg.event.get()`与`pg.key.get_pressed()` ,二者有什么区别与联系?

一、pg.event.get() 返回的是一组事件 pg.event.get() 返回的是一组事件&#xff08;一个包含多个事件对象的列表&#xff09;。这是因为在游戏的“一帧”时间内&#xff08;通常1/60秒左右&#xff09;&#xff0c;用户可能会触发多个事件&#xff08;比如同时按下多个键、快速…

TF - IDF算法面试与工作常见问题全解析

在自然语言处理领域&#xff0c;TF - IDF算法是一个基础且重要的概念。无论是在求职面试还是在实际工作中&#xff0c;都经常会遇到与TF - IDF相关的问题。以下是一些常见的问题及其详细解答&#xff1a; 一、基本概念类问题 1. 什么是TF - IDF算法&#xff1f; TF - IDF&#…

Transformer网络结构解析

博主会经常分享自己在人工智能阶段的学习笔记&#xff0c;欢迎大家访问我滴个人博客&#xff01;&#xff08;都不白来&#xff01;&#xff09; 小牛壮士 - 个人博客https://kukudelin.top/ 前言 Transformer 广泛应用于自然语言处理&#xff08;如机器翻译、文本生成&…

gateway进行接口日志打印

打印需求&#xff1a;对所有的接口打印&#xff1a;请求方式&#xff0c;请求路径&#xff0c;请求参数&#xff0c;用户id&#xff0c;访问IP&#xff0c;访问时间对增删改操作的接口打印&#xff1a;接口响应打印方案&#xff1a;给GET设置一个白名单&#xff08;因为get请求…

MATLAB实现图像增强(直方图均衡化)

直方图均衡化是一种常用的图像增强技术&#xff0c;它通过重新分布图像的像素强度值来增强图像的对比度。以下是MATLAB中实现直方图均衡化的详细方法。%% 直方图均衡变换 clc;close all;clear all;warning off;%清除变量 rand(seed, 100); randn(seed, 100); format long g;%% …

java15学习笔记-密封类

360:Sealed Classes (Preview) 封闭类&#xff08;预览&#xff09; 总结 使用密封类和接口增强Java编程语言。密封类和接口限制了哪些其他类或接口可以扩展或实现它们。这是JDK 15中的预览语言功能。 目标 允许类或接口的作者控制负责实现它的代码。 提供一种比访问…

西门子PLC通过稳联技术EtherCAT转Profinet网关连接baumuller伺服器的配置案例

西门子PLC用稳联技术的EtherCAT转Profinet网关&#xff0c;连上baumuller伺服器的配置例子本案例实现西门子S71200 PLC通过EtherCAT转Profinet网关对baumuller&#xff08;Baumller&#xff09;伺服器的实时控制&#xff0c;适用于高精度运动控制场景&#xff08;如精密机床、自…

Ansible 详细笔记

Ansible 详细笔记 一、Ansible 基础概述 1.1 定义与定位 Ansible 是由 Red Hat 主导开发的开源自动化运维工具&#xff0c;基于 Python 语言实现&#xff0c;专注于简化 IT 基础设施的配置管理、应用部署、任务编排等操作。它采用无代理架构&#xff0c;通过 SSH 协议与被控节点…

【Java 后端】Spring Boot 集成 JPA 全攻略

Spring Boot 集成 JPA 全攻略 一、前言 在 Java Web 开发中&#xff0c;数据库访问是绕不开的话题。 传统方式使用 JDBC 编写 SQL&#xff0c;维护困难、可读性差。后来有了 MyBatis 这种半自动 ORM 框架&#xff0c;再到 JPA&#xff08;Java Persistence API&#xff09;这…

pytorch学习笔记-加载现有的网络模型(VGG16)、增加/修改其中的网络层(修改为10分类)

写在前面&#xff1a;有些地方和视频里不一样的是因为官方文档更新了&#xff0c;一些参数用法不一样也很正常&#xff0c;包括我现在的也是我这个时间节点最新的&#xff0c;谁知道过段时间会不会更新呢 建议大家不要一味看视频/博客&#xff0c;多看看官方文档才是正道&#…

RocketMQ 4.9.3源码解读-NameServer组件启动流程分析

作者源码阅读笔记主要采用金山云文档记录的,所有的交互图和代码阅读笔记都是记录在云文档里面,本平台的文档编辑实在不方便,会导致我梳理的交互图和文档失去原来的格式,所以整理在文档里面,供大家阅读交流 【金山文档 | WPS云文档】 namesrv 启动流程 相关重要类介绍说明…

《嵌入式 C 语言编码规范与工程实践个人笔记》参考华为C语言规范标准

《嵌入式 C 语言编码规范与工程实践个人笔记》参考华为C语言规范标准 前言 在电子系统开发领域&#xff0c;C 语言作为底层开发的核心语言&#xff0c;其代码质量直接关系到系统的稳定性、可维护性和扩展性。良好的编码规范不仅是团队协作的基础&#xff0c;更是降低生命周期成…

纯半精度模型和全精度模型的耗时分别为248微秒和1400微秒。混合精度模型371微秒比原始模型快大约四倍!

不过有一点需要注意:在上下文管理器内部生成的任何输出,必然会采用该上下文管理器的数据类型。因此,之后我们必须将这些输出转换回FP32(例如,使用float()函数)。 with torch.autocast(device_type="cuda", dtype=torch.float16): res16 = mixed32(torch.randn…

一款开源的远程桌面软件,旨在为用户提供流畅的游戏体验,支持 2K 分辨率、60 FPS,延迟仅为 40ms。

软件介绍 CloudPlayPlus&#xff08;云玩加&#xff09;是一款令人惊艳的开源远程桌面、串流软件&#xff0c;云玩加由个人开发者开发者&#xff0c;具有四大特征&#xff1a;开源、免费、低延迟、安全。 软件使用 客户端支持多个平台&#xff0c;包括 Windows、Mac OS、安卓…

MySql——binlog和redolog的区别

目录一、binlog和redolog的区别一、binlog和redolog的区别 binlog和redolog都是存储修改的新数据&#xff0c;是否保留binlog和redolog中的一个即可。 binlog属于整个mysql&#xff0c;是所有引擎共用的&#xff0c;不是只属于innoDB引擎。而redolog属于InnoDB存储引擎。binlo…

软件著作权产生与登记关键点

知识讲解一、 软件著作权的核心特征与权利内容自动产生原则&#xff1a; 这是软件著作权最核心、最重要的特征。产生时间&#xff1a; 软件著作权自软件开发完成之日起自动产生。法律依据&#xff1a; 《中华人民共和国著作权法》第二条及《计算机软件保护条例》第五条明确规定…

什么是主成分分析(PCA)和数据降维

主成分分析&#xff08;PCA&#xff09;和数据降维是机器学习和统计学中处理高维数据的核心工具。下面用清晰的结构解释其概念、原理和应用&#xff1a; 一、数据降维&#xff08;Dimensionality Reduction&#xff09; 1. 是什么&#xff1f; 目标&#xff1a;将高维数据&…

图论(4)单源赋权最短路径算法实现(BFS实现)

目录 1. 什么是赋权最短路径 2. 赋权最短路径中的关键概念 3. Dijkstra 算法的基本思想 4. Dijkstra 算法实现&#xff08;Java&#xff09; 1. 什么是赋权最短路径 在图论中&#xff0c;最短路径问题是指在图中寻找两点之间路径总权重最小的路径问题。如果图的每条边都带…