時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
城市道路形成一棵樹。在節點放置士兵時，該士兵可看守所有與此節點相接的道路。求讓每條道路至少有一端放士兵所需的最少士兵數。
輸入格式
多組資料，讀至檔案結尾。每組先給節點數 n（0 < n ≤ 1500），再有 n 行，格式為 u:(k) v1 v2 ... vk，表示節點 u 與所列節點之間的道路。節點編號 0 到 n−1，每條邊只出現一次，列出的節點順序不固定。
輸出格式
每組輸出一行最少士兵數。
題目來源：UVa 1292 — Strategic game，CPE 歷屆試題。 原題：https://onlinejudge.org/external/12/1292.pdf
範例測資
範例輸入 1
4 0:(1) 1 1:(2) 2 3 2:(0) 3:(0) 5 3:(3) 1 4 2 1:(1) 0 2:(0) 0:(0) 4:(0)
範例輸出 1
1 2
請先登入後再提交程式碼
討論與題解
載入討論區…