IOI '08 - Cairo, Egypt

Islands

You are visiting a park which has N islands. From each island i, exactly one bridge was constructed. The length of that bridge is denoted by L_i. The total number of bridges in the park is N. Although each bridge was built from one island to another, now every bridge can be traversed in both directions. Also, for each pair of islands, there is a unique ferry that travels back and forth between them.

Since you like walking better than riding ferries, you want to maximize the sum of the lengths of the bridges you cross, subject to the constraints below.

• You can start your visit at an island of your choice.
• You may not visit any island more than once.
• At any time you may move from your current island S to another island D that you have not visited before. You can go from S to D either by:
• • Walking: Only possible if there is a bridge between the two islands. With this option the length of the bridge is added to the total distance you have walked, or
  • Ferry: You can choose this option only if D is not reachable from S using any combination of bridges and/or previously used ferries. (When checking whether it is reachable or not, you consider all paths, including paths passing through islands that you have already visited.)

Note that you do not have to visit all the islands, and it may be impossible to cross all the bridges.

Task

Write a program that, given the N bridges along with their lengths, computes the maximum distance you can walk over the bridges obeying the rules described above.

Constraints

Input

Your program must read from the standard input the following data:

• Line 1 contains the integer N, the number of islands in the park. Islands are numbered from 1 to N, inclusive.
• Each of the next N lines describes a bridge. The i^th of these lines describes the bridge constructed from island i using two integers separated by a single space. The first integer represents the island at the other endpoint of the bridge, the second integer represents the length L_i of the bridge. You may assume that for each bridge, its endpoints are always on two different islands.

Output

Your program must write to the standard output a single line containing one integer, the maximum possible walking distance.

Note 1: For some of the test cases the answer will not fit in a 32‐bit integer, you might need int64 in Pascal or long long in C/C++ to score full points on this problem.
Note 2: When running Pascal programs, it is significantly slower to read in 64‐bit data types than 32‐bit data types from standard input even when the values being read in fit in 32 bits. We recommend that you read the input data into 32‐bit data types.

Grading

For some cases worth 40% of points, N will not exceed 4,000.

Sample Input

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

Sample Output

24

The N=7 bridges in the sample are (1‐3), (2‐7), (3‐4), (4‐1), (5‐1), (6‐3) and (7‐2). Note that there are two different bridges connecting islands 2 and 7.
One way that you can achieve maximum walking distance follows:

• Start on island 5.
• Walk the bridge of length 9 to reach island 1.
• Walk the bridge of length 8 to reach island 3.
• Walk the bridge of length 4 to reach island 6.
• Take the ferry from island 6 to island 7.
• Walk the bridge of length 3 to reach island 2.

By the end you are on island 2 and your total walking distance is 9+8+4+3=24.
The only island that was not visited is island 4. Note that at the end of the trip described above you can not visit this island any more. More precisely:

• You are not able to visit it by walking, because there is no bridge connecting island 2 (where you currently stand) and island 4.
• You are not able to visit it using a ferry, because island 4 is reachable from island 2, where you currently stand. A way to reach it: use the bridge (2‐7), then use a ferry you already used to get from island 7 to island 6, then the bridge (6‐3), and finally the bridge (3‐4).

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 2.00s
Memory Limit: 128M
Added: Sep 02, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Can someone correct the ML on this one? The ML on IOI was 128 mb only.

Corrected. I have manually rejudged some submissions, but for the most part it seems no scores changed.

why am I getting a SIGSEGV?

Could be running out of memory, limit is pretty tight for this problem.

(Edited:) If I am walking on a connected component, say "A", and I use the ferry to move to other connected components, can I later on move back to "A"?

I'm under the impression that the question states this rather clearly.

Sorry, I stated my question in a wrong way. When I wrote "island", i meant "connected component of islands".

(Edit:)

Never mind, got it :)