先是看了LRJ的黑书，，没懂
又在网上找了很多文章看了看，，还是没懂。。
最后看到不知名神犇给出了算法的核心流程以及代码。。又想了很久后 终于搞懂了，
于是写下这篇文章，以后忘了还可以看看。。。
PS：由于讲的较细，篇幅较长，不过应该是讲的很清楚的。
PS：我看来，，重点就是该算法，，，以及，，，为什么要用最大生成树！
PS：之前大脑太过激动，，写搓了，，以前写的是最小生成树，，见谅啊~~~~
先用一道题目来承载我的讲解，
n个城市未连通，要修建一些路，每条路都需要一个时间ti来修建
每条路都有一个价值vi，要连通所有城市而且时间，使价值与时间之比尽量大，
而且我们不希望有不必要的浪费。。（我就想说只要n-1条路），求价值与时间的最大比值！
——————————————————————————传说中的分割线————————————————————————————
算法核心：
1.求区间[a,b];
2.根据区间中值建图 ( 图的权 vi = 价值 - (a+b)/2 * 时间 )
3.根据图计算出生成树权和 (kruskal算法)
4.若权和=0，得出答案是(a+b)/2，结束程序，若权和> 0 a = (a+b)/2，若权和< 0 b = (a+b)/2，然后继续 步骤2
算法思想：
首先明确一个思想，，一个图可以得到多个不同的比值，但该图的最大比值是唯一的，
但不同的图的最大比值可能相同！！！
我们假设原图价值与时间之比最大的时候为l
并引用一个变量xi来表示第i号路的修建与否，若xi是0,不修，是1，就修，xi只有这两种取值
那么l = ∑(xi*vi) / ∑(xi*ti) （PS：∑表示求和）
我们很容易知道
于是乎如果我们把每条边的长度用 vi - l * ti来表示的话，
绝对可以得到一个生成树的总权为0，这个显而易见嘛。。。。。
PS：是什么生成树？？
（细心的读者肯定会想：我为什么之前说是kruskal算法呢？kruskal算法是求最小最大生成树的，，
所以问题就是，为什么是求最小生成树而不是其他树呢？？这个请看完思想再看最下面的解释（按顺序来哦））
步骤1：
但实际情况是l的值我们并不知道，，但我们可以推算出一个大概范围噻。。
l肯定大于等于所有边的价值和与时间和之比噻。。然后l肯定小于等于max(vi/ti)噻
（其实还可以再精确一些，不过我们先把思路讲清楚）。。
然后我们就是在这个区间之中找出一个l使得用这个l算出的生成树的权和为0噻。。
（PS：问题就来了，这个图会有很多不同生成树于是乎会有很多权和，
可能包含权为0的生成树，但权和为0不是最大的，，按kruskal算法会得出权和>0这个结论。。
我一开始以为这是不对的，但我想了很久之后，发现这种思路蛮奇妙的！我们用求最大生成树的方法求出了
最大权和为0时的生成树！具体的你先看完思路再看最下边的解释哈。。。）
我们可以轻易的发现，l越大，最小权和越小！所以他是单调的！！（这个证明很简答嘛，读者可以自己试试）
既然是单调的，，那么我们就可以用二分啊，Dinkelbach算法什么的慢慢找噻。。
我只会二分。。就拿二分来说事。。
步骤2,3,4：
我们每次取区间[a,b]的中间值（a+b）/2来计算图的边权，然后用该图计算出生成树的权和（kruskal算法什么的。。（注意有负权边哦））
如果权和>0，那么l取大了，，最小值更新为（a+b）/2，
如果权和<0，那么l取小了，，最大值更新为（a+b）/2，
然后根据新的区间继续取，直到无线接近0了，，此时的（a+b）/2就是所需的结果了
得出结果然后输出，算法结束！
某解释：
我们有一些特定的l，计算得到一些特定的图（就是包含权值和为0的树的图）
我们要求l尽量大，l越大，图的权就越小，图的权越小，想算出权和0就得多添加权值大的边
极限情况下就是最大生成树（有点绕，，）
由于计算更新图后可能有负边，prim用不了了。，
所以只能用kruskal了！——————解释毕