| 题目名称 | 3218. [SYOI 2019] 探险 |
|---|---|
| 输入输出 | tanxia.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 .
于2019-07-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：21， 通过率：57.14% | ||||
 ShallowDream雨梨 |
100 | 0.114 s | 11.42 MiB | C++ |
|
ShallowDream雨梨 |
100 | 0.125 s | 11.42 MiB | C++ |
 Hale |
100 | 0.167 s | 137.64 MiB | C++ |
 LGLJ |
100 | 0.178 s | 8.76 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.297 s | 11.35 MiB | C++ |
 XS |
100 | 0.329 s | 38.08 MiB | C++ |
 梦那边的美好ET |
100 | 0.339 s | 38.84 MiB | C++ |
 雾茗 |
100 | 0.369 s | 47.72 MiB | C++ |
|
瑆の時間~無盡輪迴·林蔭 |
100 | 0.389 s | 22.67 MiB | C++ |
 kal0rona |
100 | 0.468 s | 54.89 MiB | C++ |
| 关于 探险 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
对不起这道题是本蒟蒻搞错意思了，题面的意思是你走过的所有路径中的权值最大，而不是权值和。
ShallowDream雨梨
2019-08-24 14:12
13楼
| ||||
|
回复 @Hale :
但是我给出的样例中，确实是不用经过1的，写了最小生成树不就错了？ ShallowDream雨梨
2019-08-24 12:51
12楼
| ||||
|
回复 @Hale :
意思是题目上说的最大值最小是对于所有人走过的路径和而不是单独每个人最小？ ShallowDream雨梨
2019-08-24 12:48
11楼
| ||||
|
回复 @ShallowDream雨梨 :
假设我们有两个点，x，y,那么他们之间的所有通路理应都是合法的，为保证题目上的所有路径最大值最小，那么在一颗最小生成树，这个最大值一定是最小的； 换一个方向理解，如果这个图不变成树，怎么树上差分啊 Hale
2019-08-24 12:37
10楼
| ||||
|
这题为什么要先写最小生成树呢？
比如样例 3 3 1 1 2 3 1 3 4 2 3 5 2 3 这个询问不应该是不经过1的吗？但写了最小生成树后路线变成2到1到3了 ShallowDream雨梨
2019-08-24 12:30
9楼
| ||||
|
思路：kruscal求一下最小生成树，然后在新树树上差分即可
| ||||
|
回复 @Hale :
这神似树剖的lca真是让在下佩服，orz%%% ShallowDream雨梨
2019-08-24 11:59
7楼
| ||||
|
回复 @ShallowDream雨梨 :
我只是不会写倍增LCA，和tarjan的LCA，QAQ，Orz Hale
2019-08-24 11:51
6楼
| ||||
|
你离AC可能只差十分钟重构
| ||||
|
树上差分+最小生成树，是个好题
ps：我本来以为自己已经很能压行了，结果hs神犇比我压得更厉害 1A留念~ ShallowDream雨梨
2019-08-24 11:39
4楼
| ||||
【题目描述】
雨停后，我们来到了一个迷宫当中（别问我怎么来的）。在这个迷宫当中有n个空地，空地之间由m条双向路相连，每一条路会有一个长度l。为了了解这里，我们决定进行探险，对于探险经过最多的点，我们怀疑就是出口，因此我希望你能帮助我们求出这个点。
我们共有k个人，每个人会选择a、b两块空地，并对中间的路进行探险。由于我们都是码农，非常~，因此我们每个人都只会让自己走的路径长之和的最大值最小。
【输入格式】
第一行3个数，分别为n、m、k。
接下来m行，每行三个字母，分别为x、y、l（分别表示x、y之间有一条长为l的双向路）。
接下来k行，每行两个字母，分别为a、b。
【输出格式】
只有一行，为可能为出口的点，再输出经过了多少次。
（如果有多个点，输出较大的点)
【样例输入】
4 6 5 2 4 29 1 3 53 1 4 54 1 2 81 3 4 37 2 3 45 1 4 3 1 2 1 1 3 2 3
【样例输出】
3 5
【提示】
对于 40%的数据，满足 n≤1000,m=n-1,k≤1000。
对于 80%的数据，满足 n≤10000,m≤105,k≤1000。
对于 100%的数据，满足 n≤5*10^4,m≤2*10^5,k≤10^5,l≤10^9。数据不保证没有重边和自环，保证每条路长度不同。