n752.
01292 - Strategic game
內容
Bob 喜歡玩電腦遊戲，特別是策略遊戲，但有時他找不到快速解決方案，這讓他非常沮喪。現在他面臨以下問題。他必須保衛一座中世紀城市，這座城市的道路形成了一棵樹。他必須在節點上放置最少數量的士兵，以便他們可以觀察所有的邊。你能幫助他嗎？ 你的程序應該找到給定樹所需放置的最少士兵數量。 例如，對於右邊的樹，解決方案是一個士兵（放在節點 1 上）。
輸入說明
輸入文件包含若干個以文本格式表示的數據集。每個數據集表示一棵樹，描述如下：
- 節點數量
- 每個節點的描述格式如下： 節點標識符：(道路數量) 節點標識符1 ... 節點標識符道路數量 或 節點標識符：(0)
節點標識符是介於 0 和 n-1 之間的整數，對於 n 個節點 (0 < n ≤ 1500)。每條邊在輸入數據中僅出現一次。
輸出說明
輸出應該打印在標準輸出上。對於每個給定的輸入數據集，打印一個整數，表示結果（最少需要的士兵數量）。每個結果應該單獨占一行。
範例輸入
#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
測資資訊：
記憶體限制：
64
MB
提示 ：
標籤:
出處:
UVA
[管理者：
ig99lp33lp33
(위즈원)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 41990 |
|
n752 | 168 | 2024-09-16 18:30 |