当前位置: 首页 > news >正文

acwing算法提高之图论--最小生成树的典型应用

目录

  • 1 介绍
  • 2 训练

1 介绍

本专题用来记录使用prim算法或kruskal算法求解的题目。

2 训练

题目1:1140最短网络

C++代码如下,

#include <iostream>
#include <cstring>using namespace std;const int N = 110, INF = 0x3f3f3f3f;
int g[N][N];
int d[N];
bool st[N];
int n, m;void prim() {memset(d, 0x3f, sizeof d);int res = 0;for (int i = 0; i < n; ++i) {int t = -1;for (int j = 1; j <= n; ++j) {if (!st[j] && (t == -1 || d[t] > d[j])) {t = j;}}st[t] = true;if (i) res += d[t];for (int j = 1; j <= n; ++j) {if (d[j] > g[t][j]) {d[j] = g[t][j];}}}cout << res << endl;return;
}int main() {cin >> n;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> g[i][j];}}prim();return 0;
}

题目2:1141局域网

C++代码如下,

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110, M = 210;
int p[N];
int n, m;struct Edge {int a, b, w;bool operator< (const Edge &W) const {return w < W.w;}
}edges[M];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {cin >> n >> m;int s = 0;for (int i = 0; i < m; ++i) {cin >> edges[i].a >> edges[i].b >> edges[i].w;s += edges[i].w;}for (int i = 1; i <= n; ++i) p[i] = i;sort(edges, edges + m);int res = 0, cnt = 0;for (int i = 0; i < m; ++i) {int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a);b = find(b);if (a != b) {p[a] = b;res += w;cnt++;}}cout << s - res << endl;return 0;
}

题目3:1142繁忙的都市

C++代码如下,

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 310, M = 8010;
int n, m;
int p[N];struct Edge {int a, b, w;bool operator< (const Edge &W) const {return w < W.w;}
}edges[M];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++i) p[i] = i;for (int i = 0; i < m; ++i) {cin >> edges[i].a >> edges[i].b >> edges[i].w;}sort(edges, edges + m);int res = 0;int cnt = 0;for (int i = 0; i < m; ++i) {int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a);b = find(b);if (a != b) {p[a] = b;cnt += 1;res = w;}}cout << cnt << " " << res << endl;return 0;
}

题目4

相关文章:

acwing算法提高之图论--最小生成树的典型应用

目录 1 介绍2 训练 1 介绍 本专题用来记录使用prim算法或kruskal算法求解的题目。 2 训练 题目1&#xff1a;1140最短网络 C代码如下&#xff0c; #include <iostream> #include <cstring>using namespace std;const int N 110, INF 0x3f3f3f3f; int g[N][N…...

springcloud基本使用二(远程调用)

创建两个springboot maven子项目 子项目名称分别为order-server和user-server 配置user-server子项目: 所需依赖: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId> </dependenc…...

代码随想录刷题day42| 01背包理论基础分割等和子集

文章目录 day41学习内容一、 01背包之二维数组解法1.1、什么是01背包1.2、动态规划五部曲1.2.1、 确定dp数组&#xff08;dp table&#xff09;以及下标的含义1.2.2、确定递推公式1.2.3、 dp数组如何初始化1.2.4、确定遍历顺序1.2.5、计算并返回最终结果 二、 01背包之一维数组…...

Python文件操作命令

文件操作 我知道你最近很累&#xff0c;是那种看不见的、身体上和精神上的疲惫感&#xff0c;但是请你一定要坚持下去。就算无人问津也好&#xff0c;技不如人也好&#xff0c;千万别让烦躁和焦虑毁了你的热情和定力。别贪心&#xff0c;我们不可能什么都有&#xff0c;也别灰心…...

CSS面试题---基础

1、css选择器及优先级 选择器优先级&#xff1a;内联样式>id选择器>类选择器、属性选择器、伪类选择器>标签选择器、微元素选择器 注意&#xff1a; !important优先级最高&#xff1b; 如果优先级相同&#xff0c;则最后出现的样式生效&#xff1b; 继承得到的样式优先…...

OpenHarmony实战开发-分布式数据管理

​介绍 本示例展示了在eTS中分布式数据管理的使用&#xff0c;包括KVManager对象实例的创建和KVStore数据流转的使用。 通过设备管理接口ohos.distributedDeviceManager &#xff0c;实现设备之间的kvStore对象的数据传输交互&#xff0c;该对象拥有以下能力详见 ;1、注册和解…...

微服务(基础篇-007-RabbitMQ部署指南)

目录 05-RabbitMQ快速入门--介绍和安装_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1LQ4y127n4?p65&vd_source60a35a11f813c6dff0b76089e5e138cc 1.单机部署 1.1.下载镜像 1.2.安装MQ 2.集群部署 2.1.集群分类 2.2.设置网络 视频地址&#xff1a; 05-Rab…...

C语言一维数组及二维数组详解

引言&#xff1a; 小伙伴们&#xff0c;我发现我正文更新的有些慢&#xff0c;但相信我&#xff0c;每一篇文章真的都很用心在写的&#xff0c;哈哈&#xff0c;在本篇博客当中我们将详细讲解一下C语言中的数组知识&#xff0c;方便大家后续的使用&#xff0c;有不会的也可以当…...

11.图像边缘检测的原理与实现

数字图像处理(19): 边缘检测算子(Roberts算子、Prewitt算子、Sobel算子 和 Laplacian算子) 数字图像处理(20): 边缘检测算子(Canny算子) 1.边缘检测介绍 1.1 边缘检测的基本原理 边缘是图像的基本特征&#xff0c;所谓的边缘就是指的图像的局部不连续性。灰度或者结构等信息的…...

RVM安装ruby笔记

环境 硬件&#xff1a;Macbook Pro 系统&#xff1a;macOS 14.1 安装公钥 通过gpg安装公钥失败&#xff0c;报错如下&#xff1a; 换了几个公钥地址&#xff08;hkp://subkeys.pgp.net&#xff0c;hkp://keys.gnupg.net&#xff0c;hkp://pgp.mit.edu&#xff09;&#xff0c;…...

电力系统负荷预测方法

电力系统负荷是什么&#xff1f; 所谓的电力负荷预测是指以电力负荷变化以及外界因素变化为基础&#xff0c;以特定的数学方法或者建立数学模型的方式为手段&#xff0c;通过对电力负荷历史数据进行分析&#xff0c;对电力系统的需求做出估计以及研究相关因素对电力负荷的影响…...

electron打包桌面版.exe之vue项目踩坑(vue3+electron 解决打包后首页打开空白,打包后路由不跳转及请求不到后端数据等问题)

vue项目https://www.qingplus.cn/components-web/index打包桌面版问题集合 一、静态资源加载问题 npm run electron_dev桌面版运行后页面空白&#xff0c;内容未加载。 填坑&#xff1a; 打包配置要用相对路径 vite.config.ts文件中的base要改成./&#xff0c;之前加了项目…...

MySQL学习笔记(持续更行ing)

级别&#xff1a; 1. 了解&#xff0c;面试概率10% 2. 掌握&#xff0c;面试概率50% 3. 重点&#xff0c;面试概率80% 目录 1. 数据库**** 1.1. 概念**** 1.2. 分类**** 1.2.1. 关系型数据库**** 1.2.1.1. SQL**** 1.2.2. 安装**** 1.2.2.1. Navicat**** 1.2.3. 非…...

服务器配置Huggingface并git clone模型和文件

服务器配置Huggingface并git clone模型和文件 参考&#xff1a;https://huggingface.co/welcome 1 注册hugging face 官网注册&#xff0c;并获取token【https://huggingface.co/settings/tokens】&#xff0c;用于登录 2 安装 2.1 安装lfs https://stackoverflow.com/qu…...

Rust 开发的高性能 HTTP 请求工具

一、简述 在现在的软件开发领域&#xff0c;HTTP请求的快速验证变得越来越重要。特别是对于后端开发人员和测试工程师来说&#xff0c;能够快速创建、执行并验证HTTP请求对于提升开发效率至关重要。近期有一个名为Hurl的开源项目&#xff0c;它被设计来高效执行HTTP请求&#…...

Android Studio 通过 WIFI 调试手机 app

操作流程 首先第一步&#xff0c;PC 和手机都需要连在同一个局域网 WIFI。 第二步&#xff0c;手机 USB 连上 PC&#xff0c;确保能查看到通过 USB 连上的设备&#xff1a; >>adb devices List of devices attached CSXasjdhwjqwjhqdh device (最好只看到一个连上的设置…...

RabbitMQ高级笔记

视频链接&#xff1a;【黑马程序员RabbitMQ入门到实战教程】 文章目录 1.发送者的可靠性1.1.生产者重试机制1.2.生产者确认机制1.3.实现生产者确认1.3.1.开启生产者确认1.3.2.定义ReturnCallback1.3.3.定义ConfirmCallback 2.MQ的可靠性2.1.数据持久化2.1.1.交换机持久化2.1.2.…...

【Qt】QtCreator交叉编译环境配置Qt mkspec

1、问题描述 在QtCreator中配置TI AM437x的交叉编译环境后,编译时报错,错误信息如下 error: gnu/stubs-soft.h: No such file or directory2、原因分析 1)环境变量CC 搜索网络,解决方法为修改交叉编译工具目录下环境配置脚本,即执行source时的文件。 本人环境为:linux…...

点点数据K参数加密逆向分析(RPC方案跟加密算法还原)

文章目录 1. 写在前面2. 接口分析3. 断点分析4. RPC调用5. 算法还原 【&#x1f3e0;作者主页】&#xff1a;吴秋霖 【&#x1f4bc;作者介绍】&#xff1a;擅长爬虫与JS加密逆向分析&#xff01;Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长…...

考研数学|《1800》+《660》精华搭配混合用(经验分享)

肯定不行&#xff0c;考研数学哪有这么容易的&#xff01; 先说说这两本习题册&#xff0c;李永乐老师推出的新版660题&#xff0c;相较于18年前的版本&#xff0c;难度略有降低&#xff0c;更加适合初学者。因此&#xff0c;对于处于基础阶段的学习者来说&#xff0c;新版660…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...