【bzoj2427】[HAOI2010]软件安装

2014年12月13日3,0064

Description

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

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

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

Input

第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 )

Output

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

Sample Input

3 10
5 5 6
2 3 4
0 1 1

Sample Output

5

题解

显然图是一些环和树

若有环必须选整个环,或者直接舍弃

将环缩点完之后变成一堆点和森林,建立虚点向所有无入度的点连边

缩点用闭包传递或者tarjan,剩下的就是个树形dp问题T T

f(i,j)表示对i及其子树花费j代价产生的最大价值

转移略

 

 

  • 伪日常系LordNanoApe2015年7月17日 下午10:52 回复

    75行的for(int k=0;k<=j;k++)
    j递增应该改为j递减,因为W有可能为0

    #1  
    • onion2015年7月18日 上午10:36 回复

      Orz KPM!

      #11
  • 弱菜lzh2015年7月20日 下午4:46 回复

    黄学长,您的代码好像有问题,提供一组测试数据
    4 10
    0 2 4 3
    1 3 2 2
    2 0 3 0

    输出应为8,但您的输出为9

    #2  
    • 垃圾2016年8月4日 上午9:18 回复

      Orz!

      #21