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

P2515 [HAOI2010] 软件安装

~~~~~      P2515 [HAOI2010] 软件安装 ~~~~~      总题单链接

思路

~~~~~      发现构成的图是一个森林和一些环。

~~~~~      对于森林,建一个虚点然后树形 D P DP DP 即可。

~~~~~      对于环,发现要么把这个环上的每一个点都选了,要么每一个都不选。所以可以先缩点。

~~~~~      缩点后跑树形 d p dp dp 就行了。

代码

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;ll n,m,v[505],w[505];
ll dfn[505],low[505],tot;
ll scc[505],din[505],cnt;
ll stk[505],ins[505],top;
vector<ll>eg[505],ng[505];
ll scw[505],scv[505],dp[505][505];void Tarjan(ll p){dfn[p]=low[p]=++tot;stk[++top]=p;ins[p]=1;for(ll v:eg[p]){if(!dfn[v]){Tarjan(v);low[p]=min(low[p],low[v]);}else if(ins[v])low[p]=min(low[p],dfn[v]);}if(low[p]==dfn[p]){cnt++;while(1){ll z=stk[top--];ins[z]=0;scc[z]=cnt;scv[cnt]+=v[z];scw[cnt]+=w[z];if(z==p)break;}}
}void dfs_dp(ll p){if(scv[p]<=m)dp[p][scv[p]]=scw[p];for(ll v:ng[p]){dfs_dp(v);for(ll i=m;i>=scv[p];i--)for(ll j=m;j>=0;j--)if(i+j<=m)dp[p][i+j]=max(dp[p][i+j],dp[p][i]+dp[v][j]);}
}signed main(){ios::sync_with_stdio(false);cin>>n>>m;for(ll i=1;i<=n;i++)cin>>v[i];for(ll i=1;i<=n;i++)cin>>w[i];for(ll i=1;i<=n;i++){ll f;cin>>f;eg[f].push_back(i);}for(ll i=1;i<=n;i++)if(!dfn[i])Tarjan(i);for(ll u=1;u<=n;u++)for(ll v:eg[u]){if(scc[u]==scc[v])continue;ng[scc[u]].push_back(scc[v]);din[scc[v]]++;}for(ll i=1;i<=cnt;i++)if(!din[i])ng[0].push_back(i);memset(dp,-0x3f,sizeof(dp));dfs_dp(0);ll ans=0;for(ll i=0;i<=m;i++)ans=max(ans,dp[scc[0]][i]);cout<<ans;return 0;
}

相关文章:

P2515 [HAOI2010] 软件安装

~~~~~ P2515 [HAOI2010] 软件安装 ~~~~~ 总题单链接 思路 ~~~~~ 发现构成的图是一个森林和一些环。 ~~~~~ 对于森林&#xff0c;建一个虚点然后树形 D P DP DP 即可。 ~~~~~ 对于环&#xff0c;发现要么把这个环上的每一个点都选了&#xff0c;要么每一个都不选。所以可以先缩…...

51单片机快速入门之定时器和计数器

51单片机快速入门之定时器 断开外部输入 晶振振荡 假设为 12MHz 12分频之后,为1MHz 当其从0-65536 时,需要65536μs 微秒 也就是65.536ms 毫秒 溢出(值>65536 时)>中断>执行中断操作 假设需要1ms后产生溢出,则需要设置初始值为64536 此时定时器会从 64536 开始计…...

【计算机网络 - 基础问题】每日 3 题(一)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/fYaBd &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏&…...

Unity全面取消Runtime费用 安装游戏不再收版费

Unity宣布他们已经废除了争议性的Runtime费用&#xff0c;该费用于2023年9月引入&#xff0c;定于1月1日开始收取。Runtime费用起初是打算根据使用Unity引擎安装游戏的次数收取版权费。2023年9月晚些时候&#xff0c;该公司部分收回了计划&#xff0c;称Runtime费用只适用于订阅…...

IDEA测试类启动报 “java: 常量字符串过长” 解决办法

目录标题 问题描述问题分析解决办法其他办法 问题描述 问题分析 字符串长度过长&#xff0c;导致 idea 默认使用的 javac 编译器编译不了。 查询资料发现&#xff0c;原因是javac在编译期间&#xff0c;常量字符串最大长度为65534。 解决办法 Javac 编译器改为 Eclipse 编译…...

计算机科学基础 -- 访存单元

访存单元&#xff08;Memory Access Unit&#xff09;的概念 访存单元&#xff08;Memory Access Unit&#xff09; 是处理器中的一个关键模块&#xff0c;负责处理指令中的内存访问操作&#xff0c;包括从内存中读取数据和将数据写入内存。由于内存访问速度通常比处理器执行速…...

Linux压缩、解压缩、查看压缩内容详解使用(tar、gzip、bzip2、xz、jar、war、aar)

在Linux环境中&#xff0c;你可以使用各种命令来压缩、解压缩和查看不同类型的压缩包。以下是常用的命令和操作说明&#xff0c;包括tar、gzip、bzip2、xz、jar、war、aar等类型的包文件。 1. tar命令&#xff1a;压缩、解压、查看tar包 压缩&#xff1a; tar -cvf archive.…...

StreamReader 和 StreamWriter提供自动处理字符编码的功能

FileStream、StreamReader 和 StreamWriter 都用于文件操作&#xff0c;但它们的设计目标和使用方式有所不同。下面是它们之间的主要差异以及如何结合使用的说明&#xff1a; 1. FileStream 用途&#xff1a;提供对文件的字节流访问&#xff0c;用于读写二进制数据。特点&…...

Gitlab备份、迁移、恢复和升级(Gitlab Backup, migration, recovery, and upgrade)

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…...

MySQL:INSERT command denied to user

异常&#xff1a; INSERT command denied to user 解决办法&#xff1a; 请检查一下 MySQL 帐号是否有相应的权限...

【Android安全】Ubuntu 16.04安装GDB和GEF

1. 安装GDB sudo apt install gdb-multiarch 2. 安装GEF(GDB Enhanced Features) 官网地址&#xff1a;https://github.com/hugsy/gef 2.1 安装2021.10版本 但是在Ubuntu 16.04上&#xff0c;bash -c "$(curl -fsSL https://gef.blah.cat/sh)"等命令不好使&…...

ISO 21434与网络安全管理系统(CSMS)的协同作用

ISO/SAE 21434与CSMS&#xff08;网络安全管理系统&#xff09;之间的关系主要体现在以下几个方面&#xff1a; 提供指导框架&#xff1a;ISO/SAE 21434《道路车辆—网络安全工程》是一项国际标准&#xff0c;它为汽车行业提供了实施网络安全管理系统的国际认可的方法和最佳实…...

Vue 67 vuex 四个map方法的使用

mapState方法&#xff1a;用于帮助我们映射state中的数据为计算属性 computed: {//借助mapState生成计算属性&#xff1a;sum、school、subject&#xff08;对象写法&#xff09;...mapState({sum:sum,school:school,subject:subject}),//借助mapState生成计算属性&#xff1a;…...

Unity自带脚本之GameObject脚本

目录 GameObject基本成员变量 静态方法 创建自带几何体 1.查找对象 通过tag来查找对象 2查找多个对象 实例化对象&#xff08;克隆对象&#xff09;的方法 删除对象的方法 过场景不移除 Unity中的Object和C#中的万物之父的区别 成员方法 创建空物体 为对象 动态添加…...

软件测试面试题-自测

一、测试流程 1.项目测试流程你是怎么开展的&#xff1f; ①首先&#xff0c;需求分析阶段&#xff0c;分析需求点&#xff0c;需求确定以后进入测试计划阶段&#xff0c;参考需求规格说明书进行测试计划编写 ②接着&#xff0c;进入测试设计阶段&#xff0c;依据需求文档及原…...

深度学习-神经网络

文章目录 一、基本组成单元&#xff1a;神经元二、神经网络层三、偏置与权重四、激活函数1.激活函数的作用2.常见的激活函数1).Sigmoid2).Tanh函数3).ReLU函数 五、优点与缺点六、总结 神经网络&#xff08;Neural Network, NN&#xff09;是一种模拟人类大脑工作方式的计算模型…...

Redis - 集群篇 - 集群模式

面试的时候被人问到集群的问题&#xff0c;搬砖仔哪懂这么多&#xff0c;继续整理一下知识点 Redis 集群模式 Redis集群就是将多个Redis节点连接在一起&#xff0c; 让Redis在不同的节点上同时提供服务。 Redis集群主要有三种模式&#xff1a; 主从复制模式&#xff08;mast…...

Robot Operating System——线速度和角速度

大纲 应用场景1. 移动机器人控制场景描述具体应用 2. 无人机控制场景描述具体应用 3. 机械臂运动控制场景描述具体应用 4. 自动驾驶车辆控制场景描述具体应用 5. 机器人仿真场景描述具体应用 6. 机器人传感器数据处理场景描述具体应用 定义字段解释 案例 geometry_msgs::msg::T…...

量化投资策略_因子打分选股的案例实现

一&#xff1a;因子打分选股的介绍 因子打分选股是一种量化投资策略&#xff0c;它通过选取多个与股票收益率相关的因子&#xff0c;对股票进行综合评分&#xff0c;然后根据评分来选择股票构建投资组合。以下是构建多因子打分选股模型的一般步骤&#xff1a; 数据预处理&…...

架构师知识梳理(七):软件工程-工程管理与开发模型

软件工程概述 软件开发生命周期 软件定义时期&#xff1a;包括可行性研究和详细需求分析过程&#xff0c;任务是确定软件开发工程必须完成的总目标&#xff0c;具体可分成问题定义、可行性研究、需求分析等。软件开发时期&#xff1a;就是软件的设计与实现&#xff0c;可分成…...

实战驱动:告诉快马你的vue项目类型,获取量身定制的环境与示例

最近在做一个Vue 3移动端H5项目时&#xff0c;发现环境配置和基础搭建特别耗时。经过几次实践&#xff0c;我总结出了一套高效的项目初始化方法&#xff0c;今天就来分享这个实战经验。 项目初始化与移动端适配 使用Vue CLI创建项目后&#xff0c;首先要解决的就是移动端适配问…...

开源工具Jellyfin豆瓣插件高效配置指南:打造完美中文媒体库

开源工具Jellyfin豆瓣插件高效配置指南&#xff1a;打造完美中文媒体库 【免费下载链接】jellyfin-plugin-douban Douban metadata provider for Jellyfin 项目地址: https://gitcode.com/gh_mirrors/je/jellyfin-plugin-douban 在数字媒体收藏日益增长的今天&#xff0…...

EN50155以太网交换机的X键位M12插座在PCB板上同一高度方法

在轨道交通车载EN50155以太网交换机的PCB设计中&#xff0c;X键位M12插座&#xff08;千兆/万兆接口&#xff09;常需多个并排或阵列布局。由于X编码插座引脚数较多&#xff08;8芯&#xff09;且结构复杂&#xff0c;确保所有插座在PCB板上的同一高度&#xff08;共面性&#…...

网页实现文字转语音朗读功能

SpeechSynthesisUtterance是HTML5中新增的API&#xff0c;用于将指定文字合成为对应的语音。 <button onclick"play()">朗读</button> <script>var utterThis new SpeechSynthesisUtterance();utterThis.text "hello word";utterThis…...

三相不平衡电压下H桥五电平并网逆变器并网控制探究

三相不平衡电压下级连H桥五电平并网逆变器并网控制&#xff0c;SPWM调制&#xff0c;正负序分离控制 1.采用正负序分离锁相环以及正序PI控制&#xff0c;负序PI控制 2.采用中点电位平衡控制-零序电压注入法 3.提供参考文献 提供仿真源文件&#xff0c;电流环参数设计&#xff0…...

智能内容解锁工具:5分钟掌握付费墙突破技巧

智能内容解锁工具&#xff1a;5分钟掌握付费墙突破技巧 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 在数字信息时代&#xff0c;优质内容常被付费墙阻隔&#xff0c;而bypass-payw…...

League-Toolkit:英雄联盟智能助手的全方位解决方案

League-Toolkit&#xff1a;英雄联盟智能助手的全方位解决方案 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 在快节奏的英雄联盟…...

AHT20传感器数据漂移?STM32硬件I2C与软件模拟的稳定性对比测试

STM32硬件I2C与软件模拟I2C在AHT20传感器应用中的稳定性深度解析 工业级环境监测系统对温湿度数据的可靠性有着严苛要求。AHT20作为一款高精度温湿度传感器&#xff0c;其数据采集的稳定性直接关系到整个系统的可信度。本文将深入探讨STM32平台下硬件I2C与GPIO模拟I2C两种实现方…...

人脸检测开源生态新成员:cv_resnet101_face-detection_cvpr22papermogface ModelScope集成详解

人脸检测开源生态新成员&#xff1a;cv_resnet101_face-detection_cvpr22papermogface ModelScope集成详解 1. 项目概述 今天要介绍的是一个特别实用的人脸检测工具——基于MogFace模型开发的本地高精度人脸检测系统。这个工具解决了PyTorch新版本加载旧模型的兼容性问题&…...

塔罗牌选框架:准确率超机器学习模型

技术选型困境与创新突破在软件测试领域&#xff0c;技术栈选择一直是核心挑战。传统方法依赖历史数据和机器学习模型&#xff0c;但常陷入“预测陷阱”——过度依赖过往经验导致创新盲区。例如&#xff0c;自动化测试框架的错误选型每年造成巨额损失&#xff1a;38.7%源于技术生…...