| 题目名称 | 2155. [SPOJ 1825] 免费旅行II |
|---|---|
| 输入输出 | freetourII.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 21 |
| 题目来源 |
 mikumikumi
于2016-02-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：66， 提交：212， 通过率：31.13% | ||||
 Hzoi_Hugh |
100 | 2.596 s | 8.90 MiB | C++ |
|
Hzoi_Hugh |
100 | 2.627 s | 8.90 MiB | C++ |
 pb0207 |
100 | 3.157 s | 8.09 MiB | C++ |
 LGLJ |
100 | 3.221 s | 16.26 MiB | C++ |
 _Itachi |
100 | 3.272 s | 10.59 MiB | C++ |
 WildRage |
100 | 3.373 s | 10.61 MiB | C++ |
 liu_runda |
100 | 3.407 s | 14.21 MiB | C++ |
|
6666 |
100 | 3.544 s | 9.83 MiB | C++ |
 Hzoi_joker |
100 | 3.675 s | 11.38 MiB | C++ |
 ONCE AGAIN |
100 | 3.805 s | 14.98 MiB | C++ |
| 关于 免费旅行II 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
[size=38]改死[/size]
| ||||
|
我想的我的代码的变量名一定有防hack的功能，然而也有防调试的功能。。
| ||||
|
第15个点可访问0个拥挤点，然而每个点都是拥挤点，答案是0，这十分不合理。
 半汪
2017-02-12 20:16
10楼
| ||||
|
| ||||
|
| ||||
|
| ||||
|
其他点正常AC.. 最后一个点地本测了27s...................
看了下数据，发现是一个菊花图带一根小棍 Σ( ° △ °|||)..... 大概算了下我能缩小到三分之一的常数..... 蓝而有p用(╯‵□′)╯︵┻━┻.... 还是看论文的算法去吧 | ||||
|
回复 @TenderRun :
OwO 最后一个点是我有权限的时候偷偷加的 OwO  Aglove
2016-07-04 19:36
5楼
| ||||
|
啊啊啊……
卡我最后一个点！！！！！ 话说漆子超的论文中神奇方法为啥会快？ | ||||
|
为什么打开O2没有超过1s的测试点，关上O2只有6个点不T？
 | ||||
哒哒哒哒哒！
MistyEye
Fmuckss
TenderRun
/k【题目描述】
在两周年纪念日的旅行之后，在第三年，旅行社SPOJ又一次踏上的打折旅行的道路。
这次旅行是ICPC岛屿上进行的，一个位于太平洋上，不可思议的小岛。我们列出了N个地点（编号从1到N）供旅客游览。这N个点由N-1条边连成一个树，每条边都有一个权值，这个权值可能为负。我们可以选择两个地点作为旅行的起点和终点。
由于当地正在庆祝节日，所以某些地方会特别的拥挤（我们称这些地方为拥挤点）。旅行的组织者希望这次旅行最多访问K个拥挤点。同时，我们希望我们经过的道路的权值和最大。
【输入格式】
第一行，三个整数N,K,M（1 <= N <= 200000, 0 <= K <=M, 0 <= M <= N）
之后的M行，每行一个拥挤点的编号。
最后的N-1行，每行三个整数u，v,l，代表u和v之间有一条权值为l的边
【输出格式】
一个整数，权值和最大的旅行线路
【样例输入】
8 2 3
3
5
7
1 3 1
2 3 10
3 4 -2
4 5 -1
5 7 6
5 6 5
4 8 3
【样例输出】
12
【提示】
在此键入。
【来源】
在此键入。