网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
岛屿
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | isl.in | 输出文件 | 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 。
样例
样例 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) 桥。