岛屿

提交数: 14, 通过率: 21.43%, 平均分: 52.5

题目描述:

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

 

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

 

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

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

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

输入格式:

你的程序要从标准输入读入以下数据：

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

输出格式:

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

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

样例输入:

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

样例输出:

24

提示:

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

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

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

1527559517377049322.png

样例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)桥。
时间限制: 2000ms
空间限制: 256MB

来源: ioi2008