[IOI2008]岛屿

Grade Open Time Friday, 19 September 2014, 10:05 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:05 am
Allow late Yes Close Time Friday, 26 September 2014, 10:05 am
Input file isl.in Output file isl.out

 

 

 

[问题描述]

    你将要游览一个有 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 。

样例

文本框: 样例输入	样例輸出  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 之间有两座不同的桥。

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

*由岛 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) 桥。