Bob 喜歡玩電腦遊戲,特別是策略遊戲,但有時他找不到快速解決方案,這讓他非常沮喪。現在他面臨以下問題。他必須保衛一座中世紀城市,這座城市的道路形成了一棵樹。他必須在節點上放置最少數量的士兵,以便他們可以觀察所有的邊。你能幫助他嗎? 你的程序應該找到給定樹所需放置的最少士兵數量。 例如,對於右邊的樹,解決方案是一個士兵(放在節點 1 上)。
輸入文件包含若干個以文本格式表示的數據集。每個數據集表示一棵樹,描述如下:
節點標識符是介於 0 和 n-1 之間的整數,對於 n 個節點 (0 < n ≤ 1500)。每條邊在輸入數據中僅出現一次。
輸出應該打印在標準輸出上。對於每個給定的輸入數據集,打印一個整數,表示結果(最少需要的士兵數量)。每個結果應該單獨占一行。
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 2
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|