[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 H: qwb与学姐 [MST+LCA]【数据结构】
[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 H: qwb与学姐 [MST+LCA]【数据结构】
2017-06-03 02:36:00 Tabris_ 阅读数:735
博客爬取于2020-06-14 22:40:15
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849743
题目链接:http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=7
——————————————————————————————————————————
Problem H: qwb与学姐
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 113 Solved: 44
[Submit][Status][Web Board]
Description
qwb打算向学姐表白,可是学姐已经受够了他的骚扰,于是出了一个题想难住他:
已知一幅n个点m条边的无向图,定义路径的值为这条路径上最短的边的长度,
现在有 k个询问,
询问从A点到B点的所有路径的值的最大值。
qwb听完这个问题很绝望啊,聪明的你能帮帮他吗?
Input
一组数据。
第一行三个整数n,m,k (1<=N<=50000,m<=200000,k<=100000)。
第2…m+1行:三个正整数:X, Y, and D (1 <= X <=N; 1 <= Y <= N,1<=D<=215) 表示X与Y之间有一条长度为D的边。
第m+2…m+k+1行: 每行两个整数A B(1<=A,B<=n且A≠B),意义如题目描述。
保证图连通。
Output
对于每个询问输出一行,一共k行,每行输出A点到B点的所有路径的值的最大值。
Sample Input
4 5 3
1 2 6
1 3 8
2 3 4
2 4 5
3 4 7
2 3
1 4
3 4
Sample Output
6
7
7
——————————————————————————————————————————
他要找所有路径的最大值,那么我只需要留校路径最大的那个就好了
这里有一个贪心策略,就是最大生成树,
这样能保证,两点间在图上其他的路径的值都小于最大生成树的
然后问题就是如何求两点间路径最小值了
最开始写了个树剖,发现由于是边权在维护的时候lca位置不好维护
于是GG,在提示下学习了倍增求lca
知识点不介绍了,
因为同样是变成了点权
我们只需要求路径最小的时候变成两个路径的最小值,非别是(u,x(fa[x]=lca)),(v,y(fa[y]=lca))
这样下来就好办多了,找到lca之后维护最小值就好了
附本题代码
——————————————————————————————————————————
1 | # include<bits/stdc++.h> |