d233. 97北縣賽-4-金幣問題 - 高中生程式解題系統

內容

4. 金幣問題

問題敘述

有一個國王想要徵求一個聰明的智者，因此他出了一道難題：在皇宮中的N個房間，每間房間都放有一個金幣，其中有些房間彼此間有直接通道。國王規定每個參加的人可以進入任一房間，並取走房間中的金幣，但不能同時取走有直接通道的兩個房間中的金幣。滿足此規定下，必須儘可能取最多的金幣，請問其中取到最多金幣的方法所得金幣數目為多少個?

舉例說明如下，有四個房間，分別以編號1到4表示，其中編號1和編號3有直接通道，編號1和編號4有直接通道。其他房間之間皆無直接通道。儘可能取金幣的方法之一為取房間1及房間2的金幣，另一個方法為取房間2, 3, 及4的金幣，共兩種取法，其中取到最多金幣的方法可取到3個金幣。

輸入說明

條件限制

  N為一大於0的正整數，最大值為255。

輸入格式

第一行輸入房間數N, 為一大於0的正整數，最大值為255。

第二行起每行輸入一組有直接通道的兩個房間編號，以空白區分。每個配對不一定依房間編號大小順序輸入。且多個配對的輸入也不一定依房間編號順序排列。讀到0表示輸入結束。

輸出說明

輸出格式

顯示可取到最多金幣的數目。

範例輸入 #1

範例輸出 #1

3
可以拿2 3 4的錢幣

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1K
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

提示：

標籤:

出處:

97學年度北基區資訊學科能力競賽 [管理者： nanj0178 (nanj) ]

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