TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2657
  • 题目
  • P2657【HAOI2010 Day1】软件安装
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    现在我们的手头有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
    第3行:V1,V2, … Vi, … ,Vn
    第4行:D1,D2, … Di, … ,Dn

    输出格式

    一个整数,代表最大价值。

    样例输入

    3 10
    5 5 6
    2 3 4
    0 1 1

    样例输出

    5


    来源  HeNanOI 2010