| 题目名称 | 444. [HAOI 2010]软件安装 |
|---|---|
| 输入输出 | install.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 .Xmz
于2010-04-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：185， 提交：471， 通过率：39.28% | ||||
 徐心雨 |
100 | 0.003 s | 0.52 MiB | C++ |
 Narcissus |
100 | 0.003 s | 0.72 MiB | C++ |
 Fmuckss |
100 | 0.003 s | 1.08 MiB | C++ |
|
Fmuckss |
100 | 0.003 s | 1.08 MiB | C++ |
 ┭┮﹏┭┮ |
100 | 0.004 s | 3.07 MiB | C++ |
 LadyLex |
100 | 0.005 s | 0.76 MiB | C++ |
 Satoshi |
100 | 0.005 s | 0.80 MiB | C++ |
 TARDIS |
100 | 0.005 s | 1.16 MiB | C++ |
 丶 |
100 | 0.005 s | 1.17 MiB | C++ |
 kZime |
100 | 0.006 s | 1.36 MiB | C++ |
| 本题关联比赛 | |||
| 树形动态规划 | |||
| 树形动态规划 | |||
| 关于 软件安装 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
tarjan + 树包 :)挺难
| ||||
|
gg了n次
人生第一道依赖背包？ 顺便复习了tarjan  CSU_Turkey
2017-09-21 06:56
14楼
| ||||
|
tarjan缩点+树包
| ||||
|
环形依赖坑坑坑
 Rapiz
2016-10-27 21:20
12楼
| ||||
|
| ||||
|
| ||||
|
回复 @魔术羊 :
我不会判环啊QAQ ！！！改了之后就过了一个点！  安呐一条小咸鱼。
2016-05-05 10:53
9楼
| ||||
|
回复 @安呐。 :
大哥，你没判环 | ||||
|
| ||||
|
嗯...缩点之后点与点之间千万不能连边...调了五分钟才发现这个问题OwQ....推荐看一波徐持衡的论文，可以写出来NM复杂度的树形背包
| ||||
~玖湫~
Respawn
Magic_Sheep
Sky_miner【问题描述】
现在我们的手头有 $N$ 个软件，对于一个软件i，它要占用 $W_i$ 的磁盘空间，它的价值为 $V_i$。我们希望从中选择一 些软件安装到一台磁盘容量为 $M$ 计算机上，使得这些软件的价值尽可能大(即 $V_i$ 的和最大)。
但是现在有个问题：软件之间存在依赖关系，即软件 $i$ 只有在安装了软件 $j$(包括软件 $j$ 的直接或间接依赖)的情况下才能正确工作(软件 $i$ 依赖软件 $j$)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 $0$。
我们现在知道了软件之间的依赖关系：软件 $i$ 依赖软件 $D_i$。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则 $D_i=0$，这时只要这个软件安装了，它就能正常工作。
【输入格式】
第 $1$ 行：$N$，$M$ $(0 \leq N \leq 100，0 \leq M \leq 500)$
第 $2$ 行：$W_1，W_2，…，W_i，…，W_n(0 \leq W_i \leq M)$
第 $3$ 行：$V_1，V_2，…，V_i，…，V_n(0 \leq V_i \leq 1000)$
第 $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