Problem : 247 - Islands

Problem Statistics

Solved Member: 9　　Submission: 118　　User Tried: 16

Statement:

你將要遊覽一個有N個島嶼的公園。從每一個島i出發，只建造一座橋。橋的長度以Li表示。公園內總共有N座橋。儘管每座橋由一個島連到另一個島，但每座橋均可以雙向行走。同時，每一對這樣的島嶼，都有一艘專用的往來兩島之間的渡船。

相對於乘船而言，你更喜歡步行。你希望所經過的橋的總長度盡可能的長，但受到以下的限制。
　　• 可以自行挑選一個島開始遊覽。
　　• 任何一個島都不能遊覽一次以上。
　　• 無論任何時間你都可以由你現在所在的島S去另一個你從未到過的島D。由S到D可以有以下方法：
　　　　o 步行：僅當兩個島之間有一座橋時才有可能。對於這種情況，橋的長度會累加到你步行的總距離；或者
　　　　o 渡船：你可以選擇這種方法，僅當沒有任何橋和/或以前使用過的渡船的組合可以由S走到D（當檢查是否可到達時，你應該考慮所有的路徑，包括經過你曾遊覽過的那些島）。

注意，你不必遊覽所有的島，也可能無法走完所有的橋。

Task:

編寫一個程序，給定N座橋以及它們的長度，按照上述的規則，計算你可以走過的橋的最大長度。

限制：
•2 <= N <= 1,000,000，公園內的島嶼數目。
•1<= Li <= 100,000,000，橋i的長度。

Input:Output:

• 第一行包含N個整數，即公園內島嶼的數目。島嶼由1到N編號。
• 隨後的N行每一行用來表示一個島。第i 行由兩個以單空格分隔的整數，表示由島i築的橋。第一個整數表示橋另一端的島，第二個整數表示該橋的長度Li。你可以假設對於每座橋，其端點總是位於不同的島上。

你的程序必須向標準輸出寫出包含一個整數的單一行，即可能的最大步行距離。

Sample Input:Sample Output:

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

HINT:

Source:

IOI 2008

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	2000ms	131072kb
1	2000ms	131072kb	3
2	2000ms	131072kb	3
3	2000ms	131072kb	3
4	2000ms	131072kb	3
5	2000ms	131072kb	3
6	2000ms	131072kb	3
7	2000ms	131072kb	3
8	2000ms	131072kb	3
9	2000ms	131072kb	3
10	2000ms	131072kb	3
11	2000ms	131072kb	3
12-1	2000ms	131072kb	3
12-2	2000ms	131072kb
13-1	2000ms	131072kb	4
13-2	2000ms	131072kb
14-1	2000ms	131072kb	10
14-2	2000ms	131072kb
14-3	2000ms	131072kb
14-4	2000ms	131072kb
15-1	2000ms	131072kb	10
15-2	2000ms	131072kb
16-1	2000ms	131072kb	10
16-2	2000ms	131072kb
16-3	2000ms	131072kb
17-1	2000ms	131072kb	10
17-2	2000ms	131072kb
17-3	2000ms	131072kb
17-4	2000ms	131072kb
18-1	2000ms	131072kb	10
18-2	2000ms	131072kb
18-3	2000ms	131072kb
18-4	2000ms	131072kb
18-5	2000ms	131072kb
18-6	4000ms	131072kb
18-7	2000ms	131072kb
19-1	2000ms	131072kb	10
19-2	2000ms	131072kb
19-3	2000ms	131072kb
19-4	2000ms	131072kb
19-5	2000ms	131072kb
19-6	2000ms	131072kb
19-7	4000ms	131072kb