关于#SZY的想念#的问题，如何解决？

Question

【问题描述】
SZY 有两个网友，他们叫 MendeZ 和 mental disablity，SZY 好久不联系他们了，对他们甚是想念，他想与他们联络。他们在一个叫?的网站上聊天，但发现网络十分卡顿，于是找管理员llq联系，llq说?中有 n 条计算机，由 n-1 条电缆相连（即为一棵树），其中第 i 条电缆连接 ai、bi 两台计算机，传输时间为 ti，网络中任意两台计算机 a、b 传输数据所需时间就是 a 到 b 的路径上所有电缆的传输时间之和，网络的效率关键在于传输时间最长的两台计算机之间传输数据所需要的时间，记为μ。现在 llq 表示将要对网络进行升级，升级的目标就是减小μ的值。对于第 i 条电缆，可以花费 pi 的价钱把它升级为光缆，光缆依然连接 ai 和 bi，不过传输时间快到可以忽略不计！现在 llq 请 SZY 选择一些电缆进行升级，使得升级之后μ的值减小的前提下，花费的价钱最少。

【输入】

输入文件名为(yearn.in)。
第一行一个整数 n。
接下来 n-1 行每行四个整数 ai、bi、ti、pi。

【输出】

输出文件名为(yearn.out)。
输出升级之后μ的值减小的前提下，花费的最少价钱

yearn1.in

4
1 2 3 3
1 3 8 33
1 4 3 7

yearn1.out

10

yearn2.in

4
1 2 3 5
2 3 5 2
3 4 5 4

yearn2.out

2

【数据范围与约定】
对于 10%的数据，1<=n<=10。
对于 40%的数据，1<=n<=1000。
对于 100% 的数据，1<=ai,bi<=n<=100000，1<=ti,pi<=10000，计算机和电缆的
编号均从 1 开始。

大家可以给我一些思路吗，谢谢！

Answer 1

在减少μ的值的前提下

这里如果只是减少μ的话，那升级两人简单路径上随意一根不就行了，题目描述有点问题耶

Answer 2

解决这个问题需要用到一种算法叫做最小生成树（Minimum Spanning Tree）算法，该算法可以在一个加权无向图上找到一棵树，使得树上所有边的权值之和最小，这正是解决 SZY 的问题所需要的。

最小生成树算法可以用 Prim 算法和 Kruskal 算法来实现。Prim 算法从图中的一个节点开始，一步步向外扩展，每次选择有最小权值的边，来连接到新的节点，直到所有节点都被连接起来。而 Kruskal 算法则是按权值从小到大的顺序，选取边，每次选取权值最小的边，直到图中所有节点都被联通起来。使用上述算法，SZY 将能够找到一棵树，使得升级之后μ的值减小的前提下，花费的最少价钱。