【题解】旅行comf HAOI2006 BZOJ1050 并查集

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1050
将近两个月前做的这道题,现在居然忘了怎么做了,又去看了一遍,算复习一下吧,干脆写起来留着以后看。
正解是这样的:既然要使得路径上最大边和最小边的比值最小,如果我们已经确定了最小值的话,那么整条路线上的最大值就应该是越小越好。所以我们可以枚举最小值,然后在图中求能使s和t连通的最小的最大值。假设说最小值为min,最大值为max,将边权在min~max之间的边全部加到图里,如果s和t连通了,则这是一个合法的方案。

阅读更多

【总结】最短路算法总结

写这篇辣鸡总结的目的

嗯我为什么会写一篇这么辣鸡的总结,主要是前几天我发现我的基础太不牢固了,连最短路都写不出来了。。。
以后要学会巩固基础,写熟基本算法。马上NOIP了,如果连这种模板都还会写错的话,大概就要退役了吧。
最短路算法,我这里想说的只有最基本的三种:Dijkstra,SPFA,Floyd。

阅读更多