博客

题目说的是秦始皇的庞大的道路体系，他想通过n-1条道路把n的城市连在一起，并且要道路的总长度minimum。有个奇葩的daoshi named Xu Fu告诉他说，他可以通过法术凭空修建一条路，并且这条路不花费金钱和人力，并且仅能修建一条道路。所以就需要考虑该把这个magic road 修在哪。。咱始皇帝命令value=A/B must be the maximum,which A is the total population of the two cities connected by the magic road,and B is the total length of none magic roads.

n太大，显然暴力枚举magic road的两端点，从而算mst，并更新最小值的思路是行不通的。所以我们想，如果这题中不存在所谓的magic road，那我们是不是进行一次最小生成树算法就可以搞定。现在我们需要保证每次选边都先把magic road选定，每次选择的时候，我们需要知道这条边是不是在最终找到的最小生成树里边，如果在，那就直接mst-这条边的长度，如果不在，那么把这条边加进去跟我们最终找到的最小生成树一定会形成环。那么接下来咱就需要找到涉及到这个magic road的所有环中第二大的边，为什么是第二大，因为找最小生成树的时候边是从小到大来找的，magic road肯定是图中最大的边。又因为我们要找的第二大的边肯定是最小生成树中的边，所以我想暴找。调试了好长时间这个部分都不成功，后来就百度找了下题解。参考了下这里的那个dfs，代码就不贴了，他解释的也挺好的。

看到他里面说这就是传说中的最优比率生成树。。但是感觉黑书里面的最优比率的分子跟分母好像都是跟边有关的东西吧，这个题分子是跟点有关的。。是人口。。算了。

我又百度了下最优比率生成树，找到三鲜大神的博客园,附上链接：

三鲜大神：

http://www.cnblogs.com/lotus3x/archive/2009/03/21/1418480.html

cicirise：

http://blog.csdn.net/cicirise/article/details/3904362

zzninGeXPerience：

http://hi.baidu.com/nelstesfeibeiyq/item/28aa46e0fd86bdc2bbf37d03

ymifa：

http://blog.sina.com.cn/s/blog_691190870101626q.html