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
公開測資點#0 (50%): 1.0s , <1M
公開測資點#1 (50%): 1.0s , <1M

提示：

標籤:

出處:

UVA [管理者： ig99lp33lp33 (위즈원) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」