|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||128 MB||21||4||4||19.048%|
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 Li. 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.
Note that you do not have to visit all the islands, and it may be impossible to cross all the bridges.
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.
Your program must read from the standard input the following data:
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 in the contest environment, 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.
7 3 8 7 2 4 2 1 4 1 9 3 4 2 3
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:
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: