| 题目名称 | 818. 通往自由的钥匙 |
|---|---|
| 输入输出 | key.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-06-15加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：45， 提交：127， 通过率：35.43% | ||||
 Ezoi_XY |
100 | 0.003 s | 0.22 MiB | Pascal |
 0 |
100 | 0.004 s | 0.35 MiB | C++ |
 葳棠殇 |
100 | 0.004 s | 0.36 MiB | C++ |
 Aglove |
100 | 0.004 s | 0.40 MiB | C++ |
 zys |
100 | 0.004 s | 0.52 MiB | C++ |
 Herian |
100 | 0.004 s | 1.54 MiB | C++ |
 Makazeu |
100 | 0.005 s | 0.36 MiB | C++ |
 HouJikan |
100 | 0.005 s | 0.36 MiB | C++ |
 落尘 |
100 | 0.005 s | 0.36 MiB | C++ |
 assassain |
100 | 0.005 s | 0.37 MiB | C++ |
| 关于 通往自由的钥匙 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
手贱写了个初始化就跪了QAQ
| ||||
|
| ||||
|
不是01背包加树归吗，怎么不对
 .CPP
2015-06-15 16:46
3楼
| ||||
|
| ||||
|
写到要吐尼玛= =边界上各种不会处理
| ||||
devil
forever
一個人的雨- 描述
-
通向自由的钥匙被放n个房间里，这n个房间由n-1条走廊连接。但是每个房间里都有特别的保护魔法，在它的作用下，我无法通过这个房间，也无法取得其中的钥匙。虽然我可以通过消耗能量来破坏房间里的魔法，但是我的能量是有限的。那么，如果我最先站在1号房间（1号房间的保护魔法依然是有效的，也就是，如果不耗费能量，我无法通过1号房间，也无法取得房间中的钥匙），如果我拥有的能量为P，我最多能取得多少钥匙？
- 输入
-
第一行包含两个非负整数，第一个为N，第二个为P。
接下来n行，按1~n的顺序描述了每个房间。第i+1行包含两个非负整数cost和keys，分别为第i件房取消魔法需要耗费的能量和房间内钥匙的数量。
接下来n-1行，每行两个非负整数x,y，表示x号房间和y号是连通的。 - 输出
- 一行一个整数，表示取得钥匙的最大值。
- 样例输入
-
5 5 1 2 1 1 1 1 2 3 3 4 1 2 1 3 2 4 2 5
- 样例输出
-
7
- 提示
-
数据范围
对于20%的测试数据，有n<=20
对于30%的测试数据，有n<=30
对于所有测试数据，有p,n<=100, cost <= Maxint, keys<= Maxint