n694. 10672 - Marbles on a tree
Tags :
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-15 13:46

Content

在一棵有根樹的頂點上放置了 n 個箱子,這些頂點編號從 1 到 n,1 ≤ n ≤ 10000。每個箱子要么是空的,要么包含一定數量的彈珠;總共有 n 顆彈珠。任務是移動彈珠,使得每個箱子恰好包含一顆彈珠。這需要通過一系列移動來完成;每次移動包括將一顆彈珠移動到相鄰頂點的箱子中。實現目標所需的最小移動次數是多少?

Input

輸入包含多個測試案例。每個案例以一個數字 n 開始,接著是 n 行。每行至少包含三個數字,分別是: 頂點的編號 v,該頂點 v 最初放置的彈珠數量,頂點 v 的子節點數量 d,接著是 d 個數字,表示 v 的子節點的編號。 當 n = 0 時,輸入結束,這一案例不應處理。

Output

對於輸入中的每個案例,輸出使每個樹的頂點上恰好有一顆彈珠所需的最小移動次數。

Sample Input #1
9
1 2 3 2 3 4
2 1 0
3 0 2 5 6
4 1 3 7 8 9
5 3 0
6 0 0
7 0 0
8 2 0
9 0 0
9
1 0 3 2 3 4
2 0 0
3 0 2 5 6
4 9 3 7 8 9
5 0 0
6 0 0
7 0 0
8 0 0
9 0 0
9
1 0 3 2 3 4
2 9 0
3 0 2 5 6
4 0 3 7 8 9
5 0 0
6 0 0
7 0 0
8 0 0
9 0 0
0
Sample Output #1
7
14
20
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」