1429 . [APIO '12] 忍者調度問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

100.0% (84/84)

Submission's AC Ratio

44.6% (209/469)

Tags

APIO 2012-APIO CKsim 2016-CKsim-5th

Description

　　在某個忍者流派中，有一位宗師。除了宗師之外，每一名忍者會有一位唯一的上司。為了維護保密性和促進領導能力，所有出動的指令皆需由上司傳送給下屬。除此之外，沒有任何其它傳送指令的方法。
　　你正準備出動一群忍者來完成客戶指派的任務。為了傳遞出動的指令，你必須選擇一名忍者作為這件任務的主持人。你能夠調度主持人可直接或間接傳達指令的每一位忍者，前提是不能超出此任務的預算。出動每位忍者的費用是固定已知的。主持人本身也可以出動。未出動的忍者可以協助傳遞出動指令，且不需付任何費用。
　　每位忍者有其領導力值。客戶的滿意度為主持人忍者的領導力值乘上出動的忍者總數。你的目標是在任務預算內，儘可能最大化客戶的滿意度。
　　給定每一位忍者 i(1≤i≤N) 的上司 Bi、 出動費用 Ci 和領導力值 Li， 以及任務總預算 M，請寫一個程式輸出預算內可達成的最大客戶滿意度。

Input Format

第一行包含兩個用空格隔開的整數 N 和 M，N 為忍者數量，M 為任務預算。
接來下來的 N 行分別是描述 N 位忍者各自的上司、出動費用和領導能力值。第 i 行包含三個用空格分開的整數 Bi,Ci,Li，其中 Bi 代表為忍者 i 的上司，而他/她的出動費用為 Ci，Li 則代表他/她的領導能力值。若 Bi=0 表示忍者 i 為宗師。Bi<i 永遠成立，即每一位忍者的上司的編號永遠都小於其本身的編號。

忍者數量（N）1≤N≤105
任務預算（M）1≤M≤109
上司（Bi）0≤Bi<N
出動費用（Ci），1≤Ci≤M
領導能力值（Li），1≤Li≤109

N≤3000 的測試資料佔分 30%。

Output Format

輸出最大客戶滿意度。

Sample Input 1

5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

Sample Output 1

6

Hints

範例測試資料中，假如我們選擇忍者 1 當主持人並且出動忍者 3 和 4 時，工資總額為 4，未超出預算 4。因為出動 2 個忍者且主持人領導能力值為 3，客戶的滿意度為 6，此為最大客戶滿意度。

Problem Source

APIO 2012
Set by Yihda Yol
建國中學105學年度校內第五次模擬賽pB

Subtasks

No. Testdata Range Score
1 0~9 30
2 0~19 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1 2
1 1000 262144 262144 1 2
2 1000 262144 262144 1 2
3 1000 262144 262144 1 2
4 1000 262144 262144 1 2
5 1000 262144 262144 1 2
6 1000 262144 262144 1 2
7 1000 262144 262144 1 2
8 1000 262144 262144 1 2
9 1000 262144 262144 1 2
10 1000 262144 262144 2
11 1000 262144 262144 2
12 1000 262144 262144 2
13 1000 262144 262144 2
14 1000 262144 262144 2
15 1000 262144 262144 2
16 1000 262144 262144 2
17 1000 262144 262144 2
18 1000 262144 262144 2
19 1000 262144 262144 2
Submit
Back to Top