题意：Hugo Heavy要从城市1到城市N运送货物，有M条道路，每条道路都有它的最大载重量，问从城市1到城市N运送最多的重量是多少。

其实题意很简单，就是找一条1-->N的路径，在不超过每条路径的最大载重量的情况下，使得运送的货物最多。

分析：其实就是找一条带权路径，使得路径上最小的权值最大化，只要求一次最大生成树即可，本也没啥复杂的算法，不过这题的解题思路让我对最小生成树有了更深的理解，在这里我讲一下我对prim算法的理解。

prim算法：

1。设有一集合S，首先，将起点s(最后就成了最小生成树的根节点)放入集合，则S = {s}

2。找到距离集合S最近的一点u，加入S集合

3。通过点u，更新其余未进入集合S的点到集合S的距离

4。如果集合S外没有点了，结束，否则转到步骤2

其实整个过程中就是在找到一个距离起点集合S路径最小的点，加入进来，然后不断更新，这就像在建一棵连通树，在保证连通的情况下，不断的加入新的叶子节点，由于每次加入的边权最小，所以最后建成的就是一棵最小生成树，它能保证起点到任意一点的路径上最小的权值最小化；同理，最大生成树就是在加点的时候找权值最大的加入就行了。

 

然后看这道题：找到一条1-->N的路径，就保证连通，最后要求最小权值最大化，就是要求路径中每条边权中的最小者最大，那么就可以用最大生成树的方法，不断地将最大权值的边加入，遇到终点N就结束，这样就不会再找到一条可以更换当前路径的更好的路径了。