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

洛谷 P1195 口袋的天空

自用。

题目传送门:口袋的天空 - 洛谷

题解:Inori_333

参考题解:题解 P1195 【口袋的天空】 - 洛谷专栏

/*P1195 口袋的天空https://www.luogu.com.cn/problem/P11952024/11/03  submit:inori333
*/#include <iostream>
#include <algorithm>
using namespace std;int n, m, k; // n个点,m条边,连成k棵树,就是说要用n个节点连出k棵树。也就是说要用n - k条边连出k棵树。 
int ans = 0;//最终的最小生成树耗费
int cnt = 0;//已经连通的边数struct edge{int u, v, w;//u,v是边的两个端点,w是边的权值
} e[200005];//边的数组int f[200005];//并查集状态数组bool cmp(edge a,edge b){return a.w < b.w;
}//重载比较函数int find(int x){if(f[x]==x)return x;elsereturn f[x] = find(f[x]);
}//并查集查找int main(){cin >> n >> m >> k;// 初始化并查集for (int i = 1; i <= n;i++){f[i] = i;}for (int i = 1; i <= m;i++){cin >> e[i].u >> e[i].v >> e[i].w;}sort(e + 1, e + 1 + m, cmp);// Kruskal算法,共m条边,所以循环m次for (int i = 1; i <= m; i++){if (find(e[i].u) != find(e[i].v)){                                   // 如果两个节点的祖宗不相等,也就是说,不会构成回路f[find(e[i].u)] = find(e[i].v); // 将他们合并成同一个祖宗ans += e[i].w;                  // 加上这条边的权值cnt++;                          // 边数加一}if(cnt==n-k)break;}if (cnt==n-k)cout << ans;elsecout<<"No Answer";return 0;
}

相关文章:

洛谷 P1195 口袋的天空

自用。 题目传送门&#xff1a;口袋的天空 - 洛谷 题解&#xff1a;Inori_333 参考题解&#xff1a;题解 P1195 【口袋的天空】 - 洛谷专栏 /*P1195 口袋的天空https://www.luogu.com.cn/problem/P11952024/11/03 submit:inori333 */#include <iostream> #include &…...

ffmpeg视频滤镜:膨胀操作-dilation

滤镜介绍 dilation 官网链接 > FFmpeg Filters Documentation 膨胀滤镜会使图片变的更亮&#xff0c;会让细节别的更明显。膨胀也是形态学中的一种操作&#xff0c;在opencv中也有响应的算子。此外膨胀结合此前腐蚀操作&#xff0c;可以构成开闭操作。 开操作是先腐蚀…...

3.3 windows,ReactOS系统中页面的换出----2,结构体PHYSICAL_PAGE

系列文章目录 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目录需要自己手动添加 例如&#xff1a;第一章 Python 机器学习入门之pandas的使用 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目…...

lvgl

lvgl 目录 lvgl Lvgl移植到STM32 -- 1、下载LVGL源码 -- 2、将必要文件复制到工程目录 -- 3、修改配置文件 将lvgl与底层屏幕结合到一块 -- lvgl也需要有定时器,专门给自己做了一个函数,告诉lvgl经过了多长时间(ms(毫秒)级别) 编写代码 lvgl的中文教程手册网站…...

【django】RESTful API 设计指南

目录 一、协议 二、域名 三、版本&#xff08;Versioning&#xff09; 四、路径&#xff08;Endpoint&#xff09; 五、HTTP动词 5.1 CRUD操作&#xff1a; 5.2 其他动词&#xff1a; 六、过滤信息&#xff08;Filtering&#xff09; 七、状态码&#xff08;Status Co…...

提升大数据量分页查询性能:深分页优化全解

前言 在处理数据量逐渐增大的数据库表时&#xff0c;优化查询性能是一个常见的挑战。朋友们可能会建议说&#xff0c;创建索引不就能解决问题了吗&#xff1f;然而&#xff0c;当数据量达到相当规模时&#xff0c;简单的索引可能不足以应对所有情况。这时&#xff0c;可能会有…...

WPF 实现冒泡排序可视化

WPF 实现冒泡排序可视化 实现冒泡排序代码就不过多讲解&#xff0c;主要是实现动画效果思路&#xff0c;本demo使用MVVM模式编写&#xff0c;读者可自行参考部分核心代码&#xff0c;即可实现如视频所示效果。 对于新手了解算法相关知识应该有些许帮助&#xff0c;至于其它类型…...

Claude 3.5 新功能 支持对 100 页的PDF 图像、图表和图形进行可视化分析

Claude 3.5 Sonnet发布PDF图像预览新功能&#xff0c;允许用户分析长度不超过100页的PDF中的视觉内容。 此功能使用户能够轻松上传文档并提取信息&#xff0c;特别适用于包含图表、图形和其他视觉元素的研究论文和技术文档。 视觉PDF分析&#xff1a;用户现在可以从包含各种视觉…...

正式开源:从 Greenplum 到 Cloudberry 迁移工具 cbcopy 发布

Cloudberry Database 作为 Greenplum 衍生版本和首选开源替代&#xff0c;由 Greenplum 原始团队成员创建&#xff0c;与 Greenplum 保持原生兼容&#xff0c;并能实现无缝迁移&#xff0c;且具备更新的 PostgreSQL 内核和更丰富的功能。GitHub: https://github.com/cloudberry…...

Python如何读写文件?

1. 文件读取 &#xff08;1&#xff09;使用open()函数打开文件 基本语法是file_object open(file_name, mode)&#xff0c;其中file_name是要打开的文件的名称&#xff08;包括路径&#xff0c;如果文件不在当前目录下&#xff09;&#xff0c;mode是打开文件的模式。例如&a…...

100种算法【Python版】第38篇——Boyer-Moore算法

本文目录 1 算法说明2 算法示例3 python代码1 算法说明 Boyer-Moore算法由Robert S. Boyer和J. Strother Moore于1977年提出,旨在提高字符串匹配的效率。该算法在寻找固定模式的过程中,利用模式本身的信息,优化搜索过程,特别适合长文本中的模式查找。 算法原理 Boyer-Moo…...

贪心算法---java---黑马

贪心算法 1)Greedy algorithm 称之为贪心算法或者贪婪算法&#xff0c;核心思想是 将寻找最优解的问题分为若干个步骤每一步骤都采用贪心原则&#xff0c;选取当前最优解因为未考虑所有可能&#xff0c;局部最优的堆叠不一定得到最终解最优 贪心算法例子 Dijkstra while …...

程序员的减压秘籍:高效与健康的平衡艺术

引言 在当今竞争激烈的科技行业中&#xff0c;程序员常常面临着极高的精神集中要求和持续的创新压力。这种工作性质让许多程序员在追求高效和创新的过程中&#xff0c;感到精疲力竭&#xff0c;面临身心健康的挑战。因此&#xff0c;找到有效的方法来缓解工作压力&#xff0c;…...

2024 年 QEMU 峰会纪要

2024 年 QEMU 峰会已于 10 月 31 日在 KVM 论坛召开&#xff0c;这是一个仅对项目中最活跃的维护者和子维护者开放的邀请会议。 出席者&#xff1a; Dan Berrang Cdric Le Goater Kevin Wolf Michael S. Tsirkin Stefan Hajnoczi Philippe Mathieu-Daud Markus Armbruster Th…...

C++/list

目录 1.list的介绍 2.list的使用 2.1list的构造 2.2list iterator的使用 2.3list capacity 2.4list element access 2.5list modifers 2.6list的迭代器失效 3.list的模拟实现 4.list与vector的对比 欢迎 1.list的介绍 list的文档介绍 cplusplus.com/reference/list/li…...

刘艳兵-DBA015-对于属于默认undo撤销表空间的数据文件的丢失,哪条语句是正确的?

对于属于默认undo撤销表空间的数据文件的丢失&#xff0c;哪条语句是正确的&#xff1f; A 所有未提交的交易都将丢失。 B 数据库实例中止。 C 数据库处于MOUNT状态&#xff0c;需要恢复才能打开。 D 数据库保持打开状态以供查询&#xff0c;但除具有SYSDBA特权的用…...

树莓派基本设置--10.使用MIPI摄像头

树莓派5将以前的CSI和DSI接口合并成两个两用的CSI/DSI&#xff08;MIPI&#xff09;端口。 一、配置摄像头 使用树莓派摄像头或第三方相机可以按照下面表格修改相机配置&#xff1a; 摄像头模块文件位于&#xff1a;/boot/firmware/config.txtV1 相机 &#xff08;OV5647&am…...

【ARCGIS实验】地形特征线的提取

目录 一、提取不同位置的地形剖面线 二、将DEM转化为TIN 三、进行可视分析 四、进行山脊、山谷等特征线的提取 1、正负地形提取&#xff08;用于校正&#xff09; 2、山脊线提取 3、山谷线的提取 4、河网的提取 5、流域的分割 五、鞍部点的提取 1、背景 2、目的 3…...

HTML 基础标签——表格标签<table>

文章目录 1. `<table>` 标签:定义表格2. `<tr>` 标签:定义表格行3. `<th>` 标签:定义表头单元格4. `<td>` 标签:定义表格单元格5. `<caption>` 标签:为表格添加标题6. `<thead>` 标签:定义表格头部7. `<tbody>` 标签:定义表格…...

线程函数和线程启动的几种不同形式

线程函数和线程启动的几种不同形式 在C中&#xff0c;线程函数和线程启动可以通过多种形式实现。以下是几种常见的形式&#xff0c;并附有相应的示例代码。 1. 使用函数指针启动线程 最基本的方式是使用函数指针来启动线程。 示例代码&#xff1a; #include <iostream&g…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...