2009 : Islands
Problem type : Batch
Time limit : 2.2 second(s)
Memory limit : 128 megabyte(s)

คุณไปเที่ยวสวนสาธารณะแห่งหนึ่งที่มีเกาะจำนวน N เกาะ จากแต่ละเกาะ i จะมีการสร้างสะพานหนึ่งสะพานทอดไปยังอีกเกาะหนึ่ง กำหนดให้สะพานนี้มีความยาว L_i ดังนั้นทั้งสวนสาธารณะจึงมีสะพานทั้งหมด N สะพาน อย่างไรก็ตาม  ถึงแม้ว่าแต่ละสะพานจะถูกสร้างจากฝั่งหนึ่งไปยังอีกฝั่งหนึ่ง สะพานเหล่านี้สามารถใช้สัญจรได้ทั้งสองทิศทาง อนึ่ง ระหว่างเกาะคู่ใด ๆ จะมีเรือหนึ่งลำแล่นไปกลับระหว่างเกาะได้

 

เนื่องจากว่าคุณชอบที่จะเดินเที่ยวมากกว่านั่งเรือ คุณจึงต้องการให้ผลรวมของความยาวของสะพานทั้งหมดที่คุณข้ามมีค่ามากที่สุด โดยมีเงื่อนไขต่อไปนี้

·       คุณเริ่มต้นการเดินทางที่เกาะใดก็ได้

·       คุณไม่แวะเกาะใดเกาะหนึ่งมากกว่าหนึ่งครั้ง

·       ณ เวลาใด ๆ คุณสามารถเดินทางจากเกาะ S ที่คุณอยู่ ไปยังเกาะ D ซึ่งเป็นเกาะที่คุณยังไม่เคยไปมาก่อน โดยที่คุณสามารถเดินทางจากเกาะ S ไปเกาะ D ได้โดยวิธีใดวิธีหนึ่งดังนี้

o      เดินไป: เป็นไปได้เฉพาะในกรณีที่ระหว่างเกาะทั้งคู่มีสะพานเชื่อม ด้วยวิธีนี้ความยาวของสะพานจะได้รับการบวกเข้ากับระยะทางรวมทั้งหมดที่คุณได้เดินมา หรือ

o      นั่งเรือ: คุณใช้วิธีนี้ได้ก็ต่อเมื่อไม่มีเส้นทางจาก S ไปถึง D ด้วยรูปแบบการเดินทางใด ๆ ด้วยสะพาน และ/หรือ เส้นทางเดินเรือที่เคยโดยสารมาก่อนหน้านี้ (รูปแบบการเดินทางที่ใช้พิจารณาเส้นทางจาก S ถึง D นี้ ให้พิจารณาทุกเส้นทางที่เป็นไปได้ ซึ่งอาจมีเกาะที่คุณเคยเดินทางไปถึงแล้ว รวมอยู่ด้วย)

หมายเหตุ: คุณไม่จำเป็นต้องไปครบทุกเกาะ และอาจจะเป็นไปไม่ได้เลยที่จะข้ามครบทุกสะพาน

โจทย์

เขียนโปรแกรมซึ่งรับจำนวนสะพาน N รวมถึงความยาวของแต่ละสะพาน จากนั้นคำนวณหาระยะทางรวมที่มากที่สุดของสะพานที่คุณเดินข้าม โดยเป็นไปตามเงื่อนไขการเดินข้างต้น

เงื่อนไข

2 ≤ N ≤ 1,000,000                   จำนวนเกาะในสวนสาธารณะ

1 ≤ L_i ≤ 100,000,000              ความยาวของสะพาน i

 

ข้อมูลนำเข้า

โปรแกรมต้องอ่านข้อมูลจาก standard input ดังนี้

·       บรรทัดที่ 1 เป็นตัวเลขจำนวนเต็ม N ซึ่งหมายถึงจำนวนเกาะในสวนสาธารณะ กำหนดให้เกาะแต่ละเกาะมีหมายเลขตั้งแต่ 1 ถึง N

·       N บรรทัดต่อมา แต่ละบรรทัดคือข้อมูลของแต่ละสะพาน บรรทัดที่ i ของข้อมูลชุดนี้คือข้อมูลของสะพานจากเกาะ i ซึ่งเป็นจำนวนเต็มสองจำนวนแยกกันด้วยช่องว่างหนึ่งช่อง จำนวนแรกแทนหมายเลขเกาะที่อยู่อีกด้านหนึ่งของสะพาน และจำนวนที่สองคือความยาวของสะพาน (L_i)  ต้นสะพานและปลายสะพานจะอยู่คนละเกาะกันเสมอ

ข้อมูลส่งออก

โปรแกรมต้องแสดงผลลัพธ์เป็นจำนวนเต็มเพียงจำนวนเดียวออกทาง standard output จำนวนเต็มนี้แสดงถึงระยะทางรวมมากที่สุดที่เดินบนสะพาน

หมายเหตุ: ข้อมูลทดสอบบางชุดอาจให้คำตอบที่เกินขอบเขตของเลขจำนวนเต็ม 32 บิต คุณอาจต้องใช้ long long ในภาษา C/C++ เพื่อให้ได้คะแนนเต็มในข้อนี้

การให้คะแนน

มีคะแนนรวมให้ 40 คะแนนสำหรับชุดทดสอบที่ N ไม่เกิน 4,000

ตัวอย่าง

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
7 3 8 7 2 4 2 1 4 1 9 3 4 2 3	24

   

 

ตัวอย่างนี้มีจำนวนสะพาน (N) เท่ากับ 7 สะพาน คือ (1-3), (2-7), (3-4), (4-1), (5-1), (6-3) และ (7-2) ขอให้ทราบว่าระหว่างเกาะ 2 และเกาะ 7 มีสะพานอยู่สองสะพาน (ที่มีความยาว 2 และ 3) เชื่อมอยู่

หนึ่งในวิธีที่คุณสามารถเดินบนสะพานได้ระยะรวมยาวที่สุด เป็นดังนี้

·       เริ่มต้นที่เกาะ 5

·       เดินผ่านสะพานความยาว 9 ไปยังเกาะ 1

·       เดินผ่านสะพานความยาว 8 ไปยังเกาะ 3

·       เดินผ่านสะพานความยาว 4 ไปยังเกาะ 6

·       ขึ้นเรือจากเกาะ 6 ไปยังเกาะ 7

·       เดินผ่านสะพานความยาว 3 ไปยังเกาะ 2

ในที่สุดคุณจะอยู่ที่เกาะ 2 ด้วยระยะทางรวมบนสะพานเป็น 9+8+4+3 = 24 โดยเกาะที่ไม่ได้แวะคือเกาะ 4 ซึ่งเป็นเกาะที่คุณไปไม่ได้อีกต่อไปหากเดินมาตามเส้นทางข้างต้นมาแล้ว เนื่องจาก

·       คุณเดินไปไม่ได้ เพราะไม่มีสะพานเชื่อมระหว่างเกาะ 2 (ที่คุณอยู่) ไปยังเกาะ 4

·       คุณขึ้นเรือไปไม่ได้ เพราะเกาะ 4 มีเส้นทางจากเกาะ 2 (ที่คุณอยู่) ไปเกาะ 4 อยู่แล้ว เส้นทางดังกล่าวคือไปตามสะพาน (2-7) แล้วขึ้นเรือจากเกาะ 7 ไปเกาะ 6 (ลำที่เคยขึ้น) จากนั้นเดินข้ามสะพาน (6-3) และสะพาน (3-4)

 

ที่มา: 20^th International Olympiad in Informatics; Cairo, Egypt (Day 1)

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
7 3 8 7 2 4 2 1 4 1 9 3 4 2 3	24

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้