OI题库

 

 

 

[问题描述]

    你将要游览一个有 N 个岛屿的公园。从每一个岛 i 出发 ，只建造一座 桥。桥的长度以 Li 表示。公园内总共有 N 座桥。 尽管每座桥由一个岛连到另一个岛，但每座桥均可以双向行走。同时，每一对这样的岛屿，都有一艘专用的往来两岛之间的渡船。

相对于乘船而言，你更喜欢步行。 你希望所经过的桥的总长度尽可能的长，但受到以下的限制。

可以自行挑选一个岛开始游览。

• 任何一个岛都不能游览一次以上。
• 无论任何时间你都可以由你现在所在的岛S 去另一个你从未到过的岛 D 。由 S 到 D 可以有以下方法：
  • 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离；或者
  • 渡船：你可以选择这种方法，仅当没有任何桥 和/或 以前使用过的渡船的组合可以由 S 走到 D （当检查是否可到达时 ，你应该考虑所有的路径，包括经过你曾游览过的那些岛）。

注意，你不必游览所有的岛，也可能无法走完所有的桥。

任务

编写一个程序，给定 N 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的最大长度。

限制

2 <= N <= 1,000,000 公园内的岛屿数目。

1<= Li <= 100,000,000 桥 i 的长度。

输入

你的程序要从输入文件读入以下数据：

• 第一行包含 N 个整数，即公园内岛屿的数目。岛屿由 1 到 N 编号。
• 随后的 N 行每一行用来表示一个岛。第 i 行由两个以单空格分隔的整数，表示由岛 i 筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度 Li 。你可以假设对於每座桥，其端点总是位于不同的岛上 。

输出

你的程序必须向输出文件写出包含一个整数的单一行，即可能的最大步行距离。

注：对某些测试，答案可能无法放进 32-bit 整数，你要取得这道题的满分，可能需要用 Pascal 的 int64 或 C/C++ 的 long long 类型。

评分

有总计 40 分的测试数据，其中 N 不会超过 4,000 。

样例

 

样例  N ＝ 7 座桥，分别为 (1-3), (2-7), (3-4), (4-1), (5-1), (6-3) 以及 (7-2) 。注意连接岛 2 与岛 7 之间有两座不同的桥。

其中一个可以取得最大的步行距离如下：

*由岛 5 开始。
*步行长度为 9 的桥到岛 1 。
*步行长度为 8 的桥到岛 3 。
*步行长度为 4 的桥到岛 6 。
*搭渡船由岛 6 到岛 7 。
*步行长度为 3 的桥到岛 2 。

最后，你到达岛 2 ，而你的总步行距离为 9 ＋ 8 ＋ 4 ＋ 3 ＝ 24 。

只有岛 4 没有去。注意，上述游览结束时，你不能再游览这个岛。更准确地说：

• 你不可以步行去游览，因为没有桥连接岛 2 （你现在的岛）与岛4 。
• 你不可以搭渡船去游览，因为你可由当前所在的岛2 到达岛 4 。一个方法是：用 (2-7) 桥，再搭你曾搭过的渡船由岛 7 去岛 6 ，然后走 (6-3) 桥，最后走 (3-4) 桥。