SP8097 IOIISL08 - 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 **Li**. The total number of bridges in the island is **N**. Each bridge can be traversed in both directions. Also, for each pair of island, 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 a visit on 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 any island D which you have not visited before. You can go from S to D either by walking, in which case the length of the bridge you take will be added to the total length or by ferry if the islands are not connected by any bridge (when checking for connectivity you should include those islands which have been previously visited by you). Note that you do not have to visit all the islands, and it may be impossible to cross al the bridges. Given N bridges along with their lengths, your task is to find out the maximum distance you can walk by following the rules above. **Constraints :** 2

N/A

N/A