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

【题解】JZOJ6578 / 洛谷P5201[USACO2019Jan]Shortcut G

洛谷 P5201 [USACO19JAN] Shortcut G

题意

在一个带权无向连通图上,每个点有 a i a_i ai 只奶牛,奶牛会走最短路径到 1 1 1,如果有多条路径,选择字典序最小的,定义移动总时间为所有奶牛走到 1 1 1 的时间之和。你可以修建一条从任意一点到 1 1 1 的边权为 t t t 的边,奶牛只有在平时走到 1 1 1 的路上看到这条边才会走。求最多能减少多少移动总时间。

题解

题目保证了对于每个点都有唯一的路径走到 1 1 1,那么可以建出一棵树,根节点为 1 1 1

然后统计一下子树中奶牛数量总和,对于每个点尝试建时间为 t t t 的新边,可以 O ( 1 ) O(1) O(1) 求出减少的移动总时间。设 j j j i i i 的子树中的节点,则减少的时间为 ( d i s i − t ) ∑ j a j (dis_i-t)\sum\limits_{j}a_j (disit)jaj

时间复杂度 O ( n ) O(n) O(n)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50005;
int n, m, t, a[N], vis[N];
LL dis[N], cnt[N], ans = 0;
int cn1 = 0, fi1[N], nx1[N << 1], to1[N << 1], va1[N << 1], cn2 = 0, fi2[N], nx2[N << 1], to2[N << 1];
void ad1(int u, int v, int w) {cn1++, nx1[cn1] = fi1[u], fi1[u] = cn1, to1[cn1] = v, va1[cn1] = w; cn1++, nx1[cn1] = fi1[v], fi1[v] = cn1, to1[cn1] = u, va1[cn1] = w;
}
void ad2(int u, int v) { cn2++, nx2[cn2] = fi2[u], fi2[u] = cn2, to2[cn2] = v; }
struct node {int r;LL dis;bool operator < (const node &T) const { return dis > T.dis; }
};
priority_queue<node> pq;
void dij(int r) {memset(dis, 0x3f, sizeof(dis)), dis[r] = 0;pq.push((node){r, 0});while (!pq.empty()) {node h = pq.top();pq.pop();if (vis[h.r]) continue;vis[h.r] = 1;for (int i = fi1[h.r]; i; i = nx1[i])if (dis[to1[i]] > dis[h.r] + va1[i])dis[to1[i]] = dis[h.r] + va1[i], pq.push((node){to1[i], dis[to1[i]]});}
}
void dfs(int r) {cnt[r] = a[r];for (int i = fi2[r]; i; i = nx2[i]) dfs(to2[i]);for (int i = fi2[r]; i; i = nx2[i]) cnt[r] += cnt[to2[i]];if (t < dis[r]) ans = max(ans, (dis[r] - t) * cnt[r]);
}
int main() {scanf("%d%d%d", &n, &m, &t);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);for (int i = 1, u, v, w; i <= m; i++) scanf("%d%d%d", &u, &v, &w), ad1(u, v, w);dij(1);for (int i = 2; i <= n; i++) {int x = n;for (int j = fi1[i]; j; j = nx1[j])if (dis[i] == dis[to1[j]] + va1[j])x = min(x, to1[j]);ad2(x, i);}dfs(1);printf("%lld", ans);return 0;
}

相关文章:

【题解】JZOJ6578 / 洛谷P5201[USACO2019Jan]Shortcut G

洛谷 P5201 [USACO19JAN] Shortcut G 题意 在一个带权无向连通图上&#xff0c;每个点有 a i a_i ai​ 只奶牛&#xff0c;奶牛会走最短路径到 1 1 1&#xff0c;如果有多条路径&#xff0c;选择字典序最小的&#xff0c;定义移动总时间为所有奶牛走到 1 1 1 的时间之和。…...

npm install sentry-cli失败的问题

1. 目前报错 2. 终端运行 npm set ENTRYCLI_CDNURLhttps://cdn.npm.taobao.org/dist/sentry-cli npm set sentrycli_cdnurlhttps://cdn.npm.taobao.org/dist/sentry-cli3. 再安装 npx sentry/wizardlatest -i nextjs即可成功...

Node opensslErrorStack 错误解决方法记录

从Git仓库中下载了一个老项目&#xff0c;使用npm install 安装后没有问题&#xff0c;当我使用npm run dev 的时候遇到了 OpenSSL 相关错误&#xff0c;例如 opensslErrorStack: [error:03000086:digital envelope routines::initialization error] 网上找了一下相关信息&am…...

你知道什么是Grandmillennial风格吗,进来看看吧

如果你既欣赏祖母的印花棉布扶手椅和大胆的图案&#xff0c;又喜欢千禧一代朋友现代家居中的开放空间和时尚家具&#xff0c;那么 "千禧一代 “风格就是为你量身打造的。它借鉴了几十年来的流行趋势&#xff0c;形成了一种独特的、带有现代风格的老式设计。 在典型的 &quo…...

App Inventor 2 开发 ChatGPT 对话App

ChatGPT大家应该不会陌生&#xff0c;它的回答内容非常的专业及深入&#xff0c;具有实际的可指导性。我们通过App Inventor 2开发一个简单的对话App&#xff0c;先看效果&#xff1a; App Inventor 2 ChatGPT教育领域对话演示 代码块如下&#xff1a; 用到的核心组件“ChatBot…...

SQL 大小敏感问题

在SQL中&#xff0c;关键字和函数名 是不区分 大小写的 比如&#xff08;select、where、order by 、group by update 等关键字&#xff09;&#xff0c;以及函数(ABS、MOD、round、min等) window系统默认是大小写不敏感 &#xff08;ZEN文件和zen 文件 不能同时存在&#xff…...

微信小程序+Taro 混编,Taro 使用微信原生 behaviors

最近有一个小程序项目&#xff0c;因为一些原因项目架构选择了微信小程序原生Taro 混编的方式进行开发&#xff0c;在开发的过程中发现 Taro 不支持使用原生的 behaviors 特性&#xff0c;因为混编的原因项目当中已有原生页面在使用 behaviors&#xff0c;所以需要一个方案在不…...

b树/b+树、时间轮、跳表、LSM-Tree

b树、b树&#xff1a;关系型数据库核心存储结构 1、为什么磁盘数据存储结构用B树、而不用红黑树 磁盘每次读取不是读一个节点、是返回一页数据。 红黑树每次遍历一个节点排除一半数据。 B树通常映射相邻的磁盘页数据。4K mysql索引一个节点隐射16k故而映射4倍&#xff0c;故…...

Unity OnDrawGizmos的简单应用 绘制圆形

编辑器和配置表各有各的好。 卡牌游戏即使再复杂&#xff0c;哪怕是梦幻西游&#xff0c;大话西游那种&#xff0c;甚至wow那种&#xff0c;用配表都完全没问题。但是崩坏3&#xff0c;或者鬼泣&#xff0c;格斗游戏&#xff0c;可视化编辑器是唯一的选择。 开发初期刚开始配技…...

Uniapp笔记(四)uniapp语法3

一、商品详情 1、从商品列表页跳转到商品详情页 在商品列表的项中绑定单击事件&#xff0c;并传递商品id值 <view class"goods-item" v-for"(item,index) in goodsList" :key"index" click"goGoodsDetail(item.goods_id)"> &…...

leetcode做题笔记105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返回其根节点。 思路一&#xff1a;递归 struct TreeNode* buildTree(int* preorder, int preorderSize, int* ino…...

Python里的列表List求和

1、使用sum()函数 numbers [1, 2, 3, 4, 5] total sum(numbers) print(total) # 输出 15 2、注意事项 在使用 sum() 函数获取列表的总和时&#xff0c;需要注意以下几点&#xff1a; sum() 函数只能用于数字类型的可迭代对象&#xff0c;如果 iterable 中包含了非数字类…...

启动docker容器的几种方法和注意事项(docker-compose,dockerfile)

1&#xff1a;要启动容器必须都先创建好镜像文件 C:\Users\dell>docker images REPOSITORY TAG IMAGE ID CREATED SIZE poi 1.0 22738bb31074 4 hours ago 105MB redis latest 506734eb5e71 6 days ago 138MB ng…...

bash: conda: command not found

问题描述&#xff1a; 在Pycharm上用SSH远程连接到服务器&#xff0c;打开Terminal准备查看用 conda 创建的虚拟环境时&#xff0c;却发现调用 conda 指令时出现以下报错&#xff1a; -bash: conda: command not found如果使用Xshell 利用端口号直接连接该 docker 容器&#…...

Leetcode-每日一题【剑指 Offer 36. 二叉搜索树与双向链表】

题目 输入一棵二叉搜索树&#xff0c;将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点&#xff0c;只能调整树中节点指针的指向。 为了让您更好地理解问题&#xff0c;以下面的二叉搜索树为例&#xff1a; 我们希望将这个二叉搜索树转化为双向循环链表…...

ctfshow-萌新专属红包题

0x00 前言 CTF 加解密合集CTF Web合集 0x01 题目 0x02 Write Up 访问之后是一个登录页面&#xff0c;扫了目录&#xff0c;试了sql注入&#xff0c;没办法于是跑一跑弱口令&#xff0c;所以有事没事&#xff0c;admin弱口令跑一跑 搜索 微信公众号 皓月当空w 发送关键字 字典…...

谷歌面试-扔鸡蛋

今天想跟大家分享一个有意思的面试题&#xff0c;这让我再一次感叹思维的奇妙&#xff0c;接下来我们一起看看吧~ 首先来看看题目&#xff1a; 你有2颗鸡蛋&#xff0c;需要以最少的尝试次数来判断在100层的高楼上&#xff0c;哪一层楼是鸡蛋的安全层。 换句话说&#xff0c…...

Unity血条制作

一、使用UGUI制作血条 我一般使用image制作血条&#xff0c;当然&#xff0c;也可以使用滑动组件Slider。image的具体操作步骤如下 普通血条 1、在Hierarchy面板中&#xff0c;创建两个image组件&#xff0c;将其中一个设置为另外一个的子节点 2、在Inspector面板中&#…...

vue,uniapp生成二维码

话不多说直接开干 先是vue的 1&#xff0c;首先按照一下依赖 npm install --save qrcode 2,在需要使用的页面引入 import QRCode from qrcode; 3,使用 const codeDetail (item) > {//这个item.code是要生成的数据&#xff0c;我的是一串数字QRCode.toDataURL(item.co…...

分类预测 | MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测

分类预测 | MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测 目录 分类预测 | MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现SSA-CNN-SVM基于麻雀算法优化卷积支持向量机分类预测…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...