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

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