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] 软件安装 ~~~~~ 总题单链接 思路 ~~~~~ 发现构成的图是一个森林和一些环。 ~~~~~ 对于森林,建一个虚点然后树形 D P DP DP 即可。 ~~~~~ 对于环,发现要么把这个环上的每一个点都选了,要么每一个都不选。所以可以先缩…...
51单片机快速入门之定时器和计数器
51单片机快速入门之定时器 断开外部输入 晶振振荡 假设为 12MHz 12分频之后,为1MHz 当其从0-65536 时,需要65536μs 微秒 也就是65.536ms 毫秒 溢出(值>65536 时)>中断>执行中断操作 假设需要1ms后产生溢出,则需要设置初始值为64536 此时定时器会从 64536 开始计…...
【计算机网络 - 基础问题】每日 3 题(一)
✍个人博客:Pandaconda-CSDN博客 📣专栏地址:http://t.csdnimg.cn/fYaBd 📚专栏简介:在这个专栏中,我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话,欢迎点赞👍收藏&…...
Unity全面取消Runtime费用 安装游戏不再收版费
Unity宣布他们已经废除了争议性的Runtime费用,该费用于2023年9月引入,定于1月1日开始收取。Runtime费用起初是打算根据使用Unity引擎安装游戏的次数收取版权费。2023年9月晚些时候,该公司部分收回了计划,称Runtime费用只适用于订阅…...
IDEA测试类启动报 “java: 常量字符串过长” 解决办法
目录标题 问题描述问题分析解决办法其他办法 问题描述 问题分析 字符串长度过长,导致 idea 默认使用的 javac 编译器编译不了。 查询资料发现,原因是javac在编译期间,常量字符串最大长度为65534。 解决办法 Javac 编译器改为 Eclipse 编译…...
计算机科学基础 -- 访存单元
访存单元(Memory Access Unit)的概念 访存单元(Memory Access Unit) 是处理器中的一个关键模块,负责处理指令中的内存访问操作,包括从内存中读取数据和将数据写入内存。由于内存访问速度通常比处理器执行速…...
Linux压缩、解压缩、查看压缩内容详解使用(tar、gzip、bzip2、xz、jar、war、aar)
在Linux环境中,你可以使用各种命令来压缩、解压缩和查看不同类型的压缩包。以下是常用的命令和操作说明,包括tar、gzip、bzip2、xz、jar、war、aar等类型的包文件。 1. tar命令:压缩、解压、查看tar包 压缩: tar -cvf archive.…...
StreamReader 和 StreamWriter提供自动处理字符编码的功能
FileStream、StreamReader 和 StreamWriter 都用于文件操作,但它们的设计目标和使用方式有所不同。下面是它们之间的主要差异以及如何结合使用的说明: 1. FileStream 用途:提供对文件的字节流访问,用于读写二进制数据。特点&…...
Gitlab备份、迁移、恢复和升级(Gitlab Backup, migration, recovery, and upgrade)
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…...
MySQL:INSERT command denied to user
异常: INSERT command denied to user 解决办法: 请检查一下 MySQL 帐号是否有相应的权限...
【Android安全】Ubuntu 16.04安装GDB和GEF
1. 安装GDB sudo apt install gdb-multiarch 2. 安装GEF(GDB Enhanced Features) 官网地址:https://github.com/hugsy/gef 2.1 安装2021.10版本 但是在Ubuntu 16.04上,bash -c "$(curl -fsSL https://gef.blah.cat/sh)"等命令不好使&…...
ISO 21434与网络安全管理系统(CSMS)的协同作用
ISO/SAE 21434与CSMS(网络安全管理系统)之间的关系主要体现在以下几个方面: 提供指导框架:ISO/SAE 21434《道路车辆—网络安全工程》是一项国际标准,它为汽车行业提供了实施网络安全管理系统的国际认可的方法和最佳实…...
Vue 67 vuex 四个map方法的使用
mapState方法:用于帮助我们映射state中的数据为计算属性 computed: {//借助mapState生成计算属性:sum、school、subject(对象写法)...mapState({sum:sum,school:school,subject:subject}),//借助mapState生成计算属性:…...
Unity自带脚本之GameObject脚本
目录 GameObject基本成员变量 静态方法 创建自带几何体 1.查找对象 通过tag来查找对象 2查找多个对象 实例化对象(克隆对象)的方法 删除对象的方法 过场景不移除 Unity中的Object和C#中的万物之父的区别 成员方法 创建空物体 为对象 动态添加…...
软件测试面试题-自测
一、测试流程 1.项目测试流程你是怎么开展的? ①首先,需求分析阶段,分析需求点,需求确定以后进入测试计划阶段,参考需求规格说明书进行测试计划编写 ②接着,进入测试设计阶段,依据需求文档及原…...
深度学习-神经网络
文章目录 一、基本组成单元:神经元二、神经网络层三、偏置与权重四、激活函数1.激活函数的作用2.常见的激活函数1).Sigmoid2).Tanh函数3).ReLU函数 五、优点与缺点六、总结 神经网络(Neural Network, NN)是一种模拟人类大脑工作方式的计算模型…...
Redis - 集群篇 - 集群模式
面试的时候被人问到集群的问题,搬砖仔哪懂这么多,继续整理一下知识点 Redis 集群模式 Redis集群就是将多个Redis节点连接在一起, 让Redis在不同的节点上同时提供服务。 Redis集群主要有三种模式: 主从复制模式(mast…...
Robot Operating System——线速度和角速度
大纲 应用场景1. 移动机器人控制场景描述具体应用 2. 无人机控制场景描述具体应用 3. 机械臂运动控制场景描述具体应用 4. 自动驾驶车辆控制场景描述具体应用 5. 机器人仿真场景描述具体应用 6. 机器人传感器数据处理场景描述具体应用 定义字段解释 案例 geometry_msgs::msg::T…...
量化投资策略_因子打分选股的案例实现
一:因子打分选股的介绍 因子打分选股是一种量化投资策略,它通过选取多个与股票收益率相关的因子,对股票进行综合评分,然后根据评分来选择股票构建投资组合。以下是构建多因子打分选股模型的一般步骤: 数据预处理&…...
架构师知识梳理(七):软件工程-工程管理与开发模型
软件工程概述 软件开发生命周期 软件定义时期:包括可行性研究和详细需求分析过程,任务是确定软件开发工程必须完成的总目标,具体可分成问题定义、可行性研究、需求分析等。软件开发时期:就是软件的设计与实现,可分成…...
从“变速齿轮”到“创新引擎”:解码阿里“大中台、小前台”战略的演进与实战
1. 中台战略的起源与本质 第一次听说"大中台、小前台"这个概念时,我正坐在杭州一家咖啡馆里和几位阿里P8的技术专家聊天。他们用了一个特别形象的比喻:"现在的互联网公司就像一辆老式自行车,前台是拼命蹬车的双腿,…...
bat脚本从入门到实战:10个常用技巧提升你的Windows自动化效率
BAT脚本从入门到实战:10个常用技巧提升你的Windows自动化效率 在Windows系统中,BAT批处理脚本就像一位不知疲倦的助手,能够24小时待命执行各种重复性任务。想象一下,每天上班第一件事是打开五个开发工具、三个文档和一个数据库客户…...
3步实现跨次元游戏模组管理:XXMI启动器的多游戏统一解决方案
3步实现跨次元游戏模组管理:XXMI启动器的多游戏统一解决方案 【免费下载链接】XXMI-Launcher Modding platform for GI, HSR, WW and ZZZ 项目地址: https://gitcode.com/gh_mirrors/xx/XXMI-Launcher 还在为《原神》《崩坏:星穹铁道》等多款二次…...
ISIS实验1
ISIS实验1网络拓扑配置一、AR1二、AR2三、测试1. 查看 IS-IS 邻居状态2. 查看 IS-IS 接口信息3. 查看 IS-IS 路由表4. 查看 IP 路由表中的 IS-IS 路由5. 查看链路状态数据库(LSDB)6. 检查:Level-1 区域一致性四、AR3五、AR4六、检测1. 通过链…...
大模型进阶必看:Agent Skills如何让AI开发更标准化、可复用?速收藏!
随着AI应用开发成熟,工具调用经历了Function Calling、MCP协议到Agent Skills三个阶段。Agent Skills通过文件系统原生设计,将指令、工作流和资源打包成可复用模块,革新上下文管理,实现代码即工具,摆脱供应商锁定。它使…...
OpenClaw智能邮件助手:nanobot镜像自动分类与回复重要邮件
OpenClaw智能邮件助手:nanobot镜像自动分类与回复重要邮件 1. 为什么需要智能邮件助手 每天早晨打开邮箱,看到堆积如山的未读邮件总是让人头疼。重要客户的询盘可能被埋没在促销广告中,紧急的协作请求可能因为延迟回复而影响项目进度。作为…...
OpenClaw隐私方案:nanobot镜像本地化部署与敏感数据处理实践
OpenClaw隐私方案:nanobot镜像本地化部署与敏感数据处理实践 1. 为什么需要本地化部署的AI助手? 去年在处理一份涉及客户隐私的法律文件时,我遇到了一个两难选择:要么手动逐条整理数百页文档,要么使用云端AI工具但面…...
3步搞定ERPNext自动化部署:让企业管理系统安装变得简单
3步搞定ERPNext自动化部署:让企业管理系统安装变得简单 【免费下载链接】erpnext_quick_install Unattended install script for ERPNext Versions, 13, 14 and 15 项目地址: https://gitcode.com/gh_mirrors/er/erpnext_quick_install 还在为复杂的ERPNext安…...
从实验室到产品:脑机接口(BCI)开发中,EEG实时预处理流程设计与避坑指南
从实验室到产品:脑机接口(BCI)开发中EEG实时预处理流程设计与避坑指南 在咖啡馆见到那位渐冻症患者用脑电波操控机械臂喝咖啡时,我意识到脑机接口技术正从实验室走向真实世界。但鲜有人提及的是,这套酷炫系统背后藏着怎样的信号处理炼狱——当…...
ViGEmBus终极指南:Windows游戏控制器虚拟化完整解决方案
ViGEmBus终极指南:Windows游戏控制器虚拟化完整解决方案 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus Windows游戏控制器虚拟化是许多PC游戏玩…...
