OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HAOI2010】软件安装

【题目描述】

现在我们的手头有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

【题解】

显然若图中有环,环上的点只能全选或全不选,所以可以Floyed传递闭包缩点,然后原图就变成了有向树森林。虚拟一个根节点连向所有有向树的根,做树形背包即可。

【代码】

累……

http://paste.ubuntu.com/11744072/

评论
热度(1)

© OI技术宅 | Powered by LOFTER