【题解】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 (disi−t)j∑aj。
时间复杂度 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 题意 在一个带权无向连通图上,每个点有 a i a_i ai 只奶牛,奶牛会走最短路径到 1 1 1,如果有多条路径,选择字典序最小的,定义移动总时间为所有奶牛走到 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仓库中下载了一个老项目,使用npm install 安装后没有问题,当我使用npm run dev 的时候遇到了 OpenSSL 相关错误,例如 opensslErrorStack: [error:03000086:digital envelope routines::initialization error] 网上找了一下相关信息&am…...

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

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

SQL 大小敏感问题
在SQL中,关键字和函数名 是不区分 大小写的 比如(select、where、order by 、group by update 等关键字),以及函数(ABS、MOD、round、min等) window系统默认是大小写不敏感 (ZEN文件和zen 文件 不能同时存在ÿ…...
微信小程序+Taro 混编,Taro 使用微信原生 behaviors
最近有一个小程序项目,因为一些原因项目架构选择了微信小程序原生Taro 混编的方式进行开发,在开发的过程中发现 Taro 不支持使用原生的 behaviors 特性,因为混编的原因项目当中已有原生页面在使用 behaviors,所以需要一个方案在不…...

b树/b+树、时间轮、跳表、LSM-Tree
b树、b树:关系型数据库核心存储结构 1、为什么磁盘数据存储结构用B树、而不用红黑树 磁盘每次读取不是读一个节点、是返回一页数据。 红黑树每次遍历一个节点排除一半数据。 B树通常映射相邻的磁盘页数据。4K mysql索引一个节点隐射16k故而映射4倍,故…...

Unity OnDrawGizmos的简单应用 绘制圆形
编辑器和配置表各有各的好。 卡牌游戏即使再复杂,哪怕是梦幻西游,大话西游那种,甚至wow那种,用配表都完全没问题。但是崩坏3,或者鬼泣,格斗游戏,可视化编辑器是唯一的选择。 开发初期刚开始配技…...
Uniapp笔记(四)uniapp语法3
一、商品详情 1、从商品列表页跳转到商品详情页 在商品列表的项中绑定单击事件,并传递商品id值 <view class"goods-item" v-for"(item,index) in goodsList" :key"index" click"goGoodsDetail(item.goods_id)"> &…...
leetcode做题笔记105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 思路一:递归 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() 函数获取列表的总和时,需要注意以下几点: sum() 函数只能用于数字类型的可迭代对象,如果 iterable 中包含了非数字类…...
启动docker容器的几种方法和注意事项(docker-compose,dockerfile)
1:要启动容器必须都先创建好镜像文件 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
问题描述: 在Pycharm上用SSH远程连接到服务器,打开Terminal准备查看用 conda 创建的虚拟环境时,却发现调用 conda 指令时出现以下报错: -bash: conda: command not found如果使用Xshell 利用端口号直接连接该 docker 容器&#…...

Leetcode-每日一题【剑指 Offer 36. 二叉搜索树与双向链表】
题目 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为双向循环链表…...

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

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

Unity血条制作
一、使用UGUI制作血条 我一般使用image制作血条,当然,也可以使用滑动组件Slider。image的具体操作步骤如下 普通血条 1、在Hierarchy面板中,创建两个image组件,将其中一个设置为另外一个的子节点 2、在Inspector面板中&#…...
vue,uniapp生成二维码
话不多说直接开干 先是vue的 1,首先按照一下依赖 npm install --save qrcode 2,在需要使用的页面引入 import QRCode from qrcode; 3,使用 const codeDetail (item) > {//这个item.code是要生成的数据,我的是一串数字QRCode.toDataURL(item.co…...

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

装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...

如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...