BZOJ 1050 [HAOI2006] 旅行 comf

发布于 2017-08-15  191 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1050

题意:求一个无向图两点间最大边权和最小边权比值最小路径。


正解即暴力,其实还是挺有趣的。

首先对所有边排个序,枚举每条边作为最小边,从这条边开始依次加入权值比它大的边,直至 ST 连通,更新答案。

判断连通性过程可以用并查集维护,时间复杂度\(O(m^2)\)

有一点需要注意的是,最小边可能已经直接满足要求了,这样直接输出 1 即可。

跑的巨慢....

 


一个非常弱的准退役OIER