网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[HAOI2010]软件安装
成绩 | 开启时间 | 2014年09月19日 星期五 10:05 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:05 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:05 |
输入文件 | install.in | 输出文件 | install.out |
【问题描述】
现在我们的手头有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)
【输出格式】
一个整数,代表最大价值。
【输入样例】
3 10
5 5 6
2 3 4
0 1 1
【输 出样例】
5