#787. [IOI2008] Island

[IOI2008] Island

[IOI2008] Island

题目描述

你准备浏览一个公园,该公园由 NN 个岛屿组成,当地管理部门从每个岛屿 ii 出发向另外一个岛屿建了一座长度为 LiL_i 的桥,不过桥是可以双向行走的。同时,每对岛屿之间都有一艘专用的往来两岛之间的渡船。相对于乘船而言,你更喜欢步行。你希望经过的桥的总长度尽可能长,但受到以下的限制:

  • 可以自行挑选一个岛开始游览。
  • 任何一个岛都不能游览一次以上。
  • 无论任何时间,你都可以由当前所在的岛 SS 去另一个从未到过的岛 DD。从 SSDD 有如下方法:
    • 步行:仅当两个岛之间有一座桥时才有可能。对于这种情况,桥的长度会累加到你步行的总距离中。
    • 渡船:你可以选择这种方法,仅当没有任何桥和以前使用过的渡船的组合可以由 SS 走到 DD (当检查是否可到达时,你应该考虑所有的路径,包括经过你曾游览过的那些岛)。

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

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

输入格式

第一行包含 NN 个整数,即公园内岛屿的数目。

随后的 NN 行每一行用来表示一个岛。第 ii 行由两个以单空格分隔的整数,表示由岛 ii 筑的桥。第一个整数表示桥另一端的岛,第二个整数表示该桥的长度 LiL_i。你可以假设对于每座桥,其端点总是位于不同的岛上。

输出格式

仅包含一个整数,即可能的最大步行距离。

样例 #1

样例输入 #1

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

样例输出 #1

24

提示

样例解释

样例图示

样例 N=7N=7 座桥,分别为 (13),(27),(34),(41),(51),(63)(1-3), (2-7), (3-4), (4-1), (5-1), (6-3) 以及 (72)(7-2)。注意连接岛 22 与岛 77 之间有两座不同的桥。

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

  • 由岛 55 开始。
  • 步行长度为 99 的桥到岛 11
  • 步行长度为 88 的桥到岛 33
  • 步行长度为 44 的桥到岛 66
  • 搭渡船由岛 66 到岛 77
  • 步行长度为 33 的桥到岛 22

最后,你到达岛 22,而你的总步行距离为 9+8+4+3=249+8+4+3=24

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

  • 你不可以步行去游览,因为没有桥连接岛 22 (你现在的岛) 与岛 44
  • 你不可以搭渡船去游览,因为你可由当前所在的岛 22 到达岛 44。一个方法是:走 (27)(2-7) 桥,再搭你曾搭过的渡船由岛 77 去岛 66,然后走 (63)(6-3) 桥,最后走 (34)(3-4) 桥。

数据范围

对于 100%100\% 的数据,$2\leqslant N\leqslant 10^6,1\leqslant L_i\leqslant 10^8$。