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

UVA1537 Picnic Planning

news 来源：原创 2025/5/18 23:29:24

题目

算法标签: 最小生成树, $k r u s ka l$ 重构树, 树形 $d p$

思路

将 $1$ 号点设置为终点, 然后执行重构树计算度数限制下的 $MST$

重构树代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>using namespace std;const int N = 60, M = N * N, INF = 0x3f3f3f3f;int n, k;struct Edge {int u, v, w;bool operator<(const Edge &e) const {return w < e.w;}
} edges[N << 1];int val[M], cnt, p[N];
map<string, int> mp;
int e_cnt;void add(int u, int v, int w) {edges[e_cnt++] = {u, v, w};
}int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int kruskal() {for (int i = 1; i <= cnt; ++i) p[i] = i;sort(edges, edges + e_cnt);int ans = 0;vector<int> vec;for (int i = 0; i < e_cnt; ++i) {auto &[u, v, w] = edges[i];int fa1 = find(u), fa2 = find(v);if (fa1 == fa2) continue;if (val[fa1] > val[fa2]) swap(fa1, fa2);p[fa2] = fa1;ans += w;//如果存在特殊边, 计算如果添加该边替换当前边的收益if (val[fa2] < INF >> 1) vec.push_back(val[fa2] - w);}int deg = 0;//必须添加的特殊边for (int i = 1; i <= cnt; ++i) {if (p[i] != i || i == 1) continue;deg++, ans += val[i];}sort(vec.begin(), vec.end());for (int i = 0; i < k - deg; ++i) ans += vec[i];return ans;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {mp.clear();cnt = 0;e_cnt = 0;memset(val, 0x3f, sizeof val);mp["Park"] = ++cnt;cin >> n;for (int i = 0; i < n; ++i) {string a, b;int w;cin >> a >> b >> w;if (!mp[a]) mp[a] = ++cnt;if (!mp[b]) mp[b] = ++cnt;int u = mp[a], v = mp[b];//先将所有和1号点连接的点断开, 并且记录最小边权if (u == 1) val[v] = min(val[v], w);else if (v == 1) val[u] = min(val[u], w);else add(u, v, w);}cin >> k;int ans = kruskal();cout << "Total miles driven: " << ans << "\n";}return 0;
}

UVA1537 Picnic Planning

目录题目算法标签: 最小生成树, k r u s k a l kruskal kruskal重构树, 树形 d p dp dp思路重构树代码题目 UVA1537 Picnic Planning 算法标签: 最小生成树, k r u s k a l kruskal kruskal重构树, 树形 d p dp dp 思路将 1 1 1号点设置为终点, 然后执行重构树计算度数…...

编程日记 2025/5/18 23:29:24

通过AWS Console连接服务器，简化运维过程

简单通过AWS Console连接您的Linux服务器本文作者: 封磊 Eclicktech SA | AWS Community Builder DevTool | AWS UGL | 亚马逊云科技云博主阿里云&InfoQ&CSDN签约作者文章目录简单通过AWS Console连接您的Linux服务器本文作者: 封磊Eclicktech SA | AWS Community …...

编程日记 2025/4/30 12:05:44

公交实时查询小程序功能点开发

线路查询：用户可输入公交线路号码，小程序实时显示该线路车辆位置与发车信息，能一键切换行驶方向，助用户依实时情况选合适候车站点。站点查询：输入车站信息，小程序呈现经过该站所有公交线路及公交信息&#…...

编程日记 2025/4/30 12:05:43

nginx配置集群服务器中的tcp负载均衡器

文章目录前言1. Ubuntu下nginx安装2. nginx的tcp负载配置前言假设一台机器支持两万的并发量，现在我们需要保证八万的并发量。首先想到的是升级服务器的配置，比如提高 CPU 执行频率，加大内存等提高机器的物理性能来解决此问题。但是单台机…...

编程日记 2025/5/18 23:21:43

Qt/C++开发监控GB28181系统/获取设备信息/设备配置参数/通道信息/设备状态

一、前言设备注册成功后，接下来要做的就是获取设备的信息，尤其是通道信息，根据国标协议，永远只有两个层级，一个是设备，然后就是设备下面多个通道，设备编码在整个系统中唯一，通道编…...

编程日记 2025/5/4 15:27:23

Linux系统基础：基础指令简介（网络概念部分）

简介：Linux 是一种开源的类 Unix 操作系统内核，由 Linus Torvalds 于 1991 年首次发布。经过多年发展，它已成为服务器、嵌入式设备和个人计算机领域的重要操作系统。网络基础概念初始协议简单来说，协议是一种约定&#xff0…...

编程日记 2025/4/30 12:04:38

labview项目文件架构

为了使 LabVIEW 项目更具可扩展性和易于维护，合理规划和设计项目文件结构是非常重要的。以下是一些基于行业经验和最佳实践的建议： 1. ### 文件夹层次划分将不同的功能模块分开存储在一个清晰的分层目录结构中是一个常见的做法。通常情况下&#xff…...

编程日记 2025/4/30 12:04:37

nuxt项目中引入并配置 iview

安装iview npm install iview --save注：想要加入其它的配置，可以在 nuxt.config.js 的 plugins 配置项中加入，同时在 plugins 文件夹下加入引入逻辑。在nuxt.config.js文件中写： {src: ~plugins/iview, ssr: true}同时新建 plugi…...

编程日记 2025/5/10 18:51:51

Origin绘图操作：点线图符号显示不全解决方法

一、问题说明在用origin绘制点线图时，图表刻度线处的点符号显示不完全，如图所示： 二、解决方法方法一：调整坐标轴刻度，使其能够显示全部数据点。方法二：有时为了图表美观，则不对坐标轴刻…...

编程日记 2025/4/30 12:02:25

【进程与线程】

文章目录一、实验目的二、实验内容与设计思想实验内容设计思路三、实验代码实现四、总结一、实验目的 1.深刻理解进程和线程的概念，掌握线程与进程在组成成分上的差别； 2.进一步认识并发执行的实质。二、实验内容与设计思想实验内容用pipe()创…...

编程日记 2025/5/18 23:23:14

项目实战-飞机大战【补档】

和项目实战-贪吃蛇大作战【补档】-CSDN博客一样，这也是一个我在大一和网友完成的项目的补档。Dont waste your youth—time flies. 目录 1.工具&环境 2.项目简介 3.需求文档 4.流程图 5.产品原型图 6.可行性分析 7.源代码 8.实战效果编辑 9.心得…...

编程日记 2025/4/30 12:02:23

算法基础学习|02归并排序——分治

一、思路 （1）确定分界点：mid(lr)/2 ——这里和快排不同 （2）递归排序（left right） （3）归并——合二为一时间复杂度nlogn 二、题目练习三、模板归并排序 …...

编程日记 2025/5/18 23:26:14

测试基础笔记第十六天

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录一、UI自动化介绍1.认识UI自动化测试2.实施UI自动化测试前置条件3.UI自动化测试执行时机4.UI自动化测试核心作用和劣势二、认识Web自动化测试工具-Selenium021.Sel…...

编程日记 2025/4/30 12:02:21

Android项目中使用ComposeUI

首先确认项目环境kotlin版本，以下是本机的版本使用命令 ./gradlew -version 这里kotlin 版本是1.5.31 然后查看build.gradle sdk版本这里是32 属于低版本然后需要添加以下配置 buildFeatures {compose true}composeOptions {kotlinCompilerExtensionVersio…...

编程日记 2025/5/6 14:42:48

springboot中有关数据库信息转换的处理

现代项目一般都是前后端分离的，前端只负责展示数据，不负责对数据处理，所以所有数据处理工作都由后端进行比如在仿京东中的status，审核信息展示，数据库中是以0/1显示，但是前端需要以"审核/未审核&quo…...

编程日记 2025/4/30 12:01:14

HHsuite同源序列搜索数据库构建

HHsuite 可用的数据库格式简介 HHsuite 是用于蛋白质序列比对和同源性检测的工具套件，它使用特定的数据库格式以实现高效的数据存储和快速的检索。HHsuite 常用的数据库格式主要基于 FFINDEX（Flat-File Index），这是一种简单而高效的文件索引系统，它将数据文件（如蛋白质序…...

编程日记 2025/5/2 23:19:21

大模型推理：Qwen3 32B vLLM Docker本地部署

Qwen3基础知识此次Qwen3开源8个模型（MOE架构：Qwen3-235B-A22B、Qwen3-30B-A3B，Dense架构：Qwen3 0.6B/1.7B/4B/8B/14B/32B），新版本的Qwen3特性包括： 支持混合思维模式，即推理/非推…...

编程日记 2025/4/30 12:00:04

第十六届蓝桥杯 2025 C/C++B组第二轮省赛全部题解（未完结）

目录前言： 试题A：密密摆放试题B：脉冲强度之和试题C：25之和试题D：旗帜试题H：破解信息前言： 这是我后续刷到的第二轮省赛的题目，我自己也做了一下，和第一轮省赛…...

编程日记 2025/4/30 11:59:00

域名转移：什么是转移码/EPP码/授权码？

关于Dynadot Dynadot是通过ICANN认证的域名注册商，自2002年成立以来，服务于全球108个国家和地区的客户，为数以万计的客户提供简洁，优惠，安全的域名注册以及管理服务。 Dynadot平台操作教程索引（包括域名邮…...

编程日记 2025/4/30 11:58:59

Android 系统发展史

Android 1.0：2008年9月全球第一台安卓设备是 HTC Dream Google地图、YouTube、HTML浏览器、Gmail、即使消息、短信、彩信、日历等 Android Market（应用程序商店） Android 1.1：2009年2月（Petit Four 花色小蛋糕&am…...

编程日记 2025/5/14 13:57:22

Python中的defaultdict方法

文章目录核心特点基本语法常见使用场景1. 分组数据（默认值为列表）2. 计数（默认值为整数）3. 集合操作（默认值为集合）4. 嵌套字典注意事项与普通字典对比总结1. 键（Key）的类型2. 值&…...

编程日记 2025/4/30 11:55:46

Android启动应用时屏蔽RecyclerView滑动，延时后再允许滑动，Kotlin

Android启动应用时屏蔽RecyclerView滑动，延时后再允许滑动，Kotlin var bCanScrollVertically falselifecycleScope.launch(Dispatchers.Default) {repeatOnLifecycle(Lifecycle.State.CREATED) {Log.d(TAG, "Lifecycle.State.CREATED")delay(…...

编程日记 2025/4/30 11:55:45

2025运维工程师面试题1(答案在后一张)

一、逻辑思维能力考核： 问题1： 3个人去投宿，一晚30元三个人每人掏了10元凑够30元交给了老板后来老板说今天优惠只要25元就够了，拿出5元命令服务生退还给他们，服务生偷偷藏起了2元，然后，把剩下…...

编程日记 2025/5/18 23:27:46

在网页中使用【LaTeX 数学公式块】的完整步骤总结

以下是在网页中使用 LaTeX 数学公式块的完整步骤总结，记录如何让网页正确渲染 LaTeX 数学表达式（如 $H(X) -\sum p(x) \log p(x)$ 这样的公式）： ✅ 使用 LaTeX 数学公式块的完整步骤（以 KaTeX 为例） &am…...

编程日记 2025/5/12 23:04:03

新人销售如何找精准客户？

深入了解自身产品或服务。清晰掌握产品优势、应用场景和解决的问题，比如销售办公软件，要熟知其提升办公效率的具体功能，以此定位需求客户。利用社交媒体平台。像领英可完善资料，加入行业群组分享内容吸引潜在客户&#xff1…...

编程日记 2025/4/30 11:53:36

【Unity】使用Socket建立客户端和服务端并进行通信的例子

Socket服务端: using System; using System.Collections.Generic; using System.Net; using System.Net.Sockets; using System.Text; using System.Threading; public class SocketServer { public static Socket listenSocket;//监听Socket public static List<Socket>…...

编程日记 2025/4/30 11:53:33

为什么要学习《易经》？

《易经》精华解读：变易之道与人生智慧《易经》（《周易》）是中国最古老的经典之一，被誉为“群经之首，大道之源”。它不仅是占卜之书，更是一部哲学经典，揭示了宇宙运行的规律和人生处世的智慧。…...

编程日记 2025/5/18 15:35:01

13.继承、重载、重写、多态、抽象类、接口、final、Static的学习

一、继承继承：你继承谁你就是谁，继承是一种严格的父子关系 （在父类里面抽取的属性和方法一定是所有子类所共有） （Student继承Person，那么Student就是人） UML: 类图（描述类和类之间的…...

编程日记 2025/4/30 11:52:28

SpringBoot Actuator未授权访问漏洞的全面解析与解决方案

引言 SpringBoot Actuator 作为应用监控与管理的核心组件，为开发者提供了丰富的系统自省和运维能力。然而，其默认配置中可能存在的未授权访问漏洞，已成为企业安全防护的潜在风险。本文将从漏洞原理、影响范围、检测方法到解决方案，系统性地剖析该问题，并提供覆盖开发、运维…...

编程日记 2025/4/30 11:52:27

使用C# ASP.NET创建一个可以由服务端推送信息至客户端的WEB应用（1）

背景用户在WEB页面上点击按钮，服务端需要执行一系列操作，该操作系列步骤较多且耗时长，为了更好的给用户浏览体验，需要在每进行一个步骤由服务端推送消息给客户端（浏览器），避免一个长时间的操作…...

编程日记 2025/4/30 11:51:24

一网统管建设组织保障分工常见表

在 “一网统管” 建设进程中，强有力的组织保障体系与各业务部门间的紧密分工协作是确保建设成效的关键。从组织保障层面来看，需建立专门的 “一网统管” 建设领导小组，由政府高层领导担任组长，各关键业务部门负责人作为组员，以此强化对整体建设工作的统筹规划与组…...

编程日记 2025/4/30 11:51:23

JVM | CMS垃圾收集器详解

目录 CMS垃圾回收器简介为什么CMS图中初始标记的阶段是单线程？为啥不多线程？当然现在默认多线程了。 CMS的两种模式与一种特殊策略 Backgroud CMS 记忆集卡表 ForeGroud CMS CMS的标记压缩算法三色标记 （便于理解而被后人提出&am…...

编程日记 2025/4/30 11:51:22

android开发中的多线程、数据存储同步功能实现方案和应用场景

在Android开发中，多线程、数据存储与同步功能有多种实现方案，以下是详细介绍及其应用场景： 多线程实现方案： Thread类与Runnable接口：通过继承Thread类并重写run方法，或实现Runnable接口并将其传入Threa…...

编程日记 2025/4/30 11:51:20

【C++初阶】--- 模板进阶

1.非类型模板参数 • 模板参数分类类型形参与非类型形参。 • 类型形参即：出现在模板参数列表中，跟在class或者typename之类的参数类型名称。 • 非类型形参，就是用一个常量作为类(函数)模板的一个参数，在类(函数)模板中可将该参…...

编程日记 2025/5/16 20:25:17

数据库所有知识

# 第一章数据库-理论基础 ## 1.1 什么是数据库数据： 描述事物的符号记录， 可以是数字、文字、图形、图像、声音、语言等，数据有多种形式，它们都可以经过数字化后存入计算机。数据库： 存储数据的仓库&#xff0c…...

编程日记 2025/5/18 23:23:15

docker部署的Nextcloud，处于维护模式，如何解决

Nextcloud 在升级后卡在维护模式，以下是针对 Docker 部署的解决方案： 1. 通过 OCC 命令强制关闭维护模式进入 Nextcloud 容器内部执行命令： # 替换 nextcloud 为你的容器名称 docker exec -it --user www-data nextcloud php occ maintena…...

编程日记 2025/5/16 9:36:02

mongoose插入文档，字段类型，字段验证，删除文档，更新文档，读取文档，查询文档的条件控制，字段筛选，数据排序，数据截取

、Mongoose 中与文档操作（插入、查询、更新、删除）及其相关功能（字段类型、验证、条件筛选、排序、分页等）相关示例： 📋 一、字段类型定义（Schema Types） const mongoose require…...

编程日记 2025/5/15 23:28:39

源码编译安装LAMP

一：LAMP概述 LAMP架构是目前成熟的企业网站应用模式之一，指的是协同工作的一整套系统和相关软件，能够提供动态Web站点服务及其应用开发环境。LAMP是一个缩写词，具体包括Linux操作系统、Apache网站服务器、MySQL数据库服务器、PHP…...

编程日记 2025/4/30 11:45:45

C++每日训练 Day 18：构建响应式表单与数据验证（初学者友好）

📘 本篇目标：在前几日协程与事件驱动机制基础上，构建一个响应式表单系统，实现用户输入的异步验证与反馈。通过协程挂起/恢复机制，简化异步逻辑，提升代码可读性。 🔁 回顾 Day 17：响应…...

编程日记 2025/5/11 13:39:43

Linux环境变量以及进程虚拟地址原理

目录一、介绍进程优先级 1.什么是优先级 2.为什么会有优先级 3.Linux中的优先级是怎么确定的 1）查看Linux中的优先级 2）计算优先级和更改优先级二、环境变量 1.什么是环境变量 2.环境变量有什么作用 3.环境变量怎么做到的 1）查看系统已有的…...

编程日记 2025/5/8 19:15:11

基于非递归求解的汉诺塔超级计算机堆栈与数据区设计方案

基于非递归求解的汉诺塔超级计算机堆栈与数据区设计方案一、设计背景与目标汉诺塔问题存在非递归直接求解方法，相较于递归法具有明确移动规律和潜在性能优势。本设计旨在利用非递归求解规律，优化汉诺塔超级计算机的堆栈与数据区结构，降低…...

编程日记 2025/4/30 11:44:38

【Linux应用】在PC的Linux环境下通过chroot运行ARM虚拟机镜像img文件（需要依赖qemu-aarch64、不需要重新安装iso）

【Linux应用】在PC的Linux环境下通过chroot运行ARM虚拟机镜像img文件（需要依赖qemu-aarch64、不需要重新安装iso） qemu提供了运行ARM虚拟机的方法具体的操作方式就是建立一个硬盘img 然后通过iso安装到img 最后再运行img即可这种方式教程很多很简单 …...

编程日记 2025/4/30 11:44:37

CISC与RISC详解：定义、区别及典型处理器

一、CISC（复杂指令集计算机） Complex Instruction Set Computer 核心思想：通过设计复杂的指令，减少程序指令数量，以硬件复杂度换取编程便利性。主要特点： 指令复杂度高： 单条指令可完成多步操…...

编程日记 2025/4/30 11:44:34

数据库中DDL、DML、DCL的区别是什么？

数据库中DDL、DML、DCL的区别是什么？ 在数据库的使用过程中，SQL（结构化查询语言）常常被用来执行不同的操作，主要分为三类：DDL（数据定义语言）、DML（数据操纵语言&#xf…...

编程日记 2025/5/14 20:08:03

【东枫电子】AI-RAN：人工智能 - 无线接入网络

太原市东枫电子科技有限公司，翻译文章目录 1.概述1.1 什么是AI-RAN？1.2 为什么是AI-RAN？1.3 AI-RAN有哪些好处？1.4 为什么 AI-RAN 会给通信服务提供商 (CoSP) 带来变革？1.5 AIRAN 的构建模块是什么？ 2. 参…...

编程日记 2025/4/30 11:43:30

实习技能记录【5】-----项目中消息传递到ui层的方法

代码 while (1){osEvent evt;evt osMailGet(ui_msg_mailbox, 0);if (evt.status osEventMail){UI_MSG_APP_T *msg (UI_MSG_APP_T *)evt.value.p;if (msg->cmd_type CMD_TYPE_INNER){if (msg->cmd_code CMD_CODE_INNER_REFRESH_NOW){lv_obj_invalidate(lv_scr_act()…...

编程日记 2025/5/13 14:35:37