2011年8月26日 星期五

539 - The Settlers of Catan



1995年推出的遊戲"卡坦島拓荒"(Settlers of Catan)曾榮獲德國年度遊戲大賞,玩家們必須在資源豐沛的荒島上拓荒,在未知的領域上開拓殖民地、建造道路與城市。你現在被雇用來設計該遊戲的電腦版本,並請你實作該遊戲的的一項特殊規則:路王

遊戲結束時,擁有最長道路的玩家為路王,並獲得額外的三分獎勵。

問題是每個玩家所建造的道路網路較為複雜,並非只是直線路段,所以決定最長路徑並非一項易事(但通常人眼可以直覺的分辨出來)。
不同於原始遊戲有制定許多額外的規則,例如當道路被對方玩家以城市截斷時,不計入總長度,在此我們不必考慮這些額外的規則,只需考慮最簡化的情況: 給定一些節點(城市)與連接節點且長度為1的邊(路段),最長的路徑限定為網路內同一個邊只計算一次的路徑,但同個節點可拜訪超過一次。
例如下圖網路中,最長路徑長為12。

o        o -- o        o
 \      /      \      /
  o -- o        o -- o
 /      \      /      \
o        o -- o        o -- o
               \      /
                o -- o

Input

輸入有多組測試資料。每組測試資料的第一列有兩個整數:n (2 <= n <= 25)表示節點數,m (1 <= m <= 25)表示邊數,接下來有 m 列,每列表示一個連接兩個節點的邊,節點的編號為0 ~ n-1,邊沒有方向性,一個節點最多連接三個邊,網路並非是連通的。
當 n = m = 0 表示測試資料結束。

Output

請針對每組測試資料輸出最長路徑長度。

Sample Input 

3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
0 0

Sample Output 

2
12


原文出處

沒有留言:

張貼留言