Problem : 326 - Rivers

Problem Statistics

Solved Member: 12　　Submission: 44　　User Tried: 14

Statement:

拜特王國是一個以出產木材聞名的國家，整個國家被木材與河流覆蓋，小河流會匯集成大河流。所有的河流最後匯集成一條大河，再從拜特鎮出海。

拜特王國裡共有n 個住有伐木工人的鄉鎮 ( 不包括拜特鎮 ) ，這些鄉鎮都有一條往外流且不分歧的河流，木頭可以因此隨著水流流至另一個鄉鎮，由於河水只會往下流，所以最後都可以流到拜特鎮，在拜特鎮中，有一個木材加工廠會處理王國裡的木頭。

水運的成本非常高，1根木頭流1公里需要花費1拜特幣，國王為了降低成本，決定在n個鄉鎮中選k個鄉鎮興建木材加工廠，如此一來木頭便不用運輸到拜特鎮，而可以在順流而下的第一個木材加工廠處理即可。

王國的財務大臣統計了每個鄉鎮所出產的木頭數目。請你幫忙決定應該在哪增設木材加工廠，使得水運的成本最低。

Task:

請寫一個程式來：

　　♦ 讀入鄉鎮數，每一鄉鎮所砍的樹木量，及相鄰河流的資訊，
　　♦ 計算在新增了木材加工廠後，藉由河流運送樹木的最低成本，
　　♦ 將答案輸出。

Input:Output:

第一行有兩個數字n, k，分別代表鄉鎮數量( 不包括拜特鎮 )與可增設的木材加工廠數量，其中2 ≤ n ≤ 100, 1 ≤ k ≤ 50, 且k ≤ n，鄉鎮以1, 2, 3, … n作為編號，而拜特鎮以0作為編號。

接下來的 n 行各有三個整數，各以一個空白隔開。第i + 1行有：

　　♦ Wi ─ 每年從鄉鎮 i 所砍的樹木量 (0 ≤ Wi ≤ 10000)

　　♦ Vi ─ 從鄉鎮 i 往下流的第一個鄉鎮(可能為拜特鎮) (0 ≤ Vi ≤ n)

　　♦ Di ─ 從鄉鎮 i 流到另一個鄉鎮的距離(1 ≤ Di ≤ 10000)，單位是公里

我們保證運送所有樹木到木材加工廠的總成本不超過 2000000000元。

在 50% 的測試資料中，n 不會超過 20。

輸出一個數字，即藉由河流運輸所有木頭的最低成本。

Sample Input:Sample Output:

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

HINT:

輸入範例的圖示如下。鄉鎮號碼顯示在圓圈裡，圓圈下的數字代表每年在該鄉鎮所砍下的木頭量。箭頭上的數字代表該段河流的長度。

範例中，新的木材加工廠應該蓋在鄉鎮2 和鄉鎮3。

Source:

IOI 2005

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	32768kb
1	1000ms	32768kb	5
2	1000ms	32768kb	5
3	1000ms	32768kb	5
4	1000ms	32768kb	5
5	1000ms	32768kb	5
6	1000ms	32768kb	5
7	1000ms	32768kb	5
8	1000ms	32768kb	5
9	1000ms	32768kb	5
10	1000ms	32768kb	5
11	1000ms	32768kb	5
12	1000ms	32768kb	5
13	1000ms	32768kb	5
14	1000ms	32768kb	5
15	1000ms	32768kb	5
16	1000ms	32768kb	5
17	1000ms	32768kb	5
18	1000ms	32768kb	5
19	1000ms	32768kb	5
20	1000ms	32768kb	5