#10774: 給卡在line3或line4的朋友提示


a5083 (assassin刺客大師)

學校 : 新北市立板橋高級中學
編號 : 28347
來源 : [140.116.138.99]
最後登入時間 :
2017-06-27 17:13:56
c111. 00315 - Network -- UVa315 | From: [140.123.56.163] | 發表日期 : 2016-03-12 18:12

若你是卡在line3的話,要注意critical point的定義

首先我來考你

若連接圖形是

7

1 2 4

2 3 5

4 5

5 6

6 7

0

則critical point為2 5 6

為何1 4 不是呢

因為與1相連的2 4即使少了1,2還是能連到4

與4相連的1 5即使少了4,1還是能連到5

所以把這點修正就可以解決line3的問題了

(用bfs)

 

至於line4的話

則是要注意題目輸入的連接點可能有n+1個

舉個例

輸入可能是

7

1 2 4

2 3 5

3 5

4 5

5 6

6 7

7 6

0

 

希望有幫到遇到wa的朋友

 
ZeroJudge Forum