#P2515. [HAOI2010] 软件安装
[HAOI2010] 软件安装
题目描述
现在我们的手头有个软件,对于一个软件i,它要占用的磁盘空间,它的价值为。我们希望从中选择一些软件安装到一台磁盘容量为计算机上,使得这些软件的价值尽可能大(即的和最大)。
但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件(包括软件j的直接或间接依赖)的情况下才能正确工作(软件依赖软件)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为。
我们现在知道了软件之间的依赖关系:软件i依赖软件。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则,这时只要这个软件安装了,它就能正常工作。
输入格式
第1行:
第2行:
第3行:
第4行:$D_1, D_2, ..., D_i, ..., D_n (0\leq D_i\leq N, D_i≠i)$
输出格式
一个整数,代表最大价值
3 10
5 5 6
2 3 4
0 1 1
5