次小生成树.java

package graph.最小生成树拓展;

/**
 * https://blog.csdn.net/qq_41661919/article/details/86565228
 * Input
 * 5 6
 * 1 2 1
 * 1 3 2
 * 2 4 3
 * 3 5 4
 * 3 4 3
 * 4 5 6
 * Output
 * 11
 * 先求出最小生成树，并建树图，之后遍历所有非树边，用树上倍增
 * 求LCA的方法求出非树边两节点之间树边中的最大边和次大边，再将非
 * 树边权值与最大值比较，如果最大边<非树边（或者不等于，不等于一
 * 定<，要不然最小生成树就不是最小了）权值，用非树边替换最大边，否
 * 则（等于关系）用非树边替换次大边，最后从所有候选答案中选择最小值
 * 即次小生成树权值。
 */
public class 次小生成树 {
    public static void main(String[] args) {

    }
}