P2515 [HAOI2010]软件安装

    • 592通过
    • 2.2K提交
  • 题目提供者 a384162546
  • 评测方式 云端评测
  • 标签 Tarjan 动态规划,动规,dp 强连通分量,缩点 各省省选 2010 河南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。

    但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为0。

    我们现在知道了软件之间的依赖关系:软件i依赖软件Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这时只要这个软件安装了,它就能正常工作。

    输入输出格式

    输入格式:

    第1行:N, M (0<=N<=100, 0<=M<=500)

    第2行:W1, W2, ... Wi, ..., Wn (0<=Wi<=M )

    第3行:V1, V2, ..., Vi, ..., Vn (0<=Vi<=1000 )

    第4行:D1, D2, ..., Di, ..., Dn (0<=Di<=N, Di≠i )

    输出格式:

    一个整数,代表最大价值

    输入输出样例

    输入样例#1: 复制
    3 10
    5 5 6
    2 3 4
    0 1 1
    输出样例#1: 复制
    5
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。