当前位置: 首页 > 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基于麻雀算法优化卷积支持向量机分类预测…...

5个理由告诉你为什么Karate是API测试自动化的终极解决方案

5个理由告诉你为什么Karate是API测试自动化的终极解决方案 【免费下载链接】karate Test Automation Made Simple 项目地址: https://gitcode.com/gh_mirrors/ka/karate Karate测试框架是一个革命性的开源工具&#xff0c;它将API测试、Mock服务、性能测试和UI自动化完美…...

PyTorch实战:基于ResNet-50的室内场景图像分类(附完整代码与MIT67数据集处理)

1. 室内场景分类与ResNet-50实战概述 室内场景分类是计算机视觉中的经典任务&#xff0c;比如区分客厅、厨房、卧室等不同功能区域。这个任务看似简单&#xff0c;但实际应用中会遇到光照变化、视角差异、物体遮挡等挑战。我去年参与过一个智能家居项目&#xff0c;就遇到过摄像…...

从SNAP到ENVI:手把手教你处理哨兵2A数据并计算6种植被指数(附完整代码)

从SNAP到ENVI&#xff1a;哨兵2A数据处理与六种植被指数全流程实战指南 在遥感生态监测领域&#xff0c;哨兵2A数据因其10-60米的空间分辨率和13个光谱波段的丰富信息&#xff0c;已成为植被动态研究的重要数据源。然而从原始数据到可用指标&#xff0c;需要经历复杂的预处理和…...

PKSM终极指南:从Gen I到Gen VIII的宝可梦存档管理神器

PKSM终极指南&#xff1a;从Gen I到Gen VIII的宝可梦存档管理神器 【免费下载链接】PKSM Gen I to GenVIII save manager. 项目地址: https://gitcode.com/gh_mirrors/pk/PKSM 你是否曾因宝可梦游戏存档意外损坏而痛心疾首&#xff1f;是否在跨世代转移精灵时遇到数据兼…...

别再用老方法了!手把手教你用Coilcraft在线工具搞定BUCK电感选型(附避坑指南)

别再用老方法了&#xff01;手把手教你用Coilcraft在线工具搞定BUCK电感选型&#xff08;附避坑指南&#xff09; 在电源设计领域&#xff0c;BUCK电路因其高效、稳定的特性成为工程师们的首选方案。然而&#xff0c;电感选型这个看似简单的环节却让不少资深工程师栽过跟头——…...

【独家首发】Midjourney啤酒印相失效诊断手册:识别8类常见色偏/纹理崩坏场景并实时修复

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Midjourney Beer印相技术原理与失效本质 Midjourney Beer印相&#xff08;非官方术语&#xff0c;实为社区对特定图像生成伪影的戏称&#xff09;并非真实存在的官方技术&#xff0c;而是用户在使用 Mi…...

Cadence CIS库与原理图同步避坑指南:为什么更新了库,图纸上的元件属性还是旧的?

Cadence CIS库与原理图同步避坑指南&#xff1a;为什么更新了库&#xff0c;图纸上的元件属性还是旧的&#xff1f; 在电子设计自动化&#xff08;EDA&#xff09;领域&#xff0c;Cadence的Component Information System&#xff08;CIS&#xff09;被广泛用于管理元件库与原理…...

收藏!小白程序员必看:AI应用黄金三年,普通人如何入局高薪岗位?

文章分析了AI应用与智能体时代的就业趋势&#xff0c;指出AI正在重塑岗位能力结构并创造新职业。未来三年&#xff0c;AI应用工程师、AI自动化运营、AI产品经理等岗位需求大、门槛低&#xff0c;适合普通人入局。文章建议从建立AI知识体系、掌握关键技能、完成AI项目入手&#…...

Android二进制XML解析终极指南:AXMLPrinter2完整使用手册

Android二进制XML解析终极指南&#xff1a;AXMLPrinter2完整使用手册 【免费下载链接】AXMLPrinter2 AXMLPrinter jar and zip files from Google Code 项目地址: https://gitcode.com/gh_mirrors/ax/AXMLPrinter2 在Android应用开发与逆向分析领域&#xff0c;开发者经…...

5分钟快速上手:通达信缠论量化插件完整使用指南

5分钟快速上手&#xff1a;通达信缠论量化插件完整使用指南 【免费下载链接】Indicator 通达信缠论可视化分析插件 项目地址: https://gitcode.com/gh_mirrors/ind/Indicator 通达信缠论量化插件是一款专为股票投资者设计的缠论技术分析工具&#xff0c;能够将复杂的缠论…...