题解 ： https://xiaoxiaoh.blog.csdn.net/article/details/104264502

一、内容

小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： 如果最小生成树选择的边集是 EM，严格次小生成树选择的边集是 ES，那么需要满足：(value(e) 表示边 e的权值) 这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

Input

第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

Output

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

Sample Input

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

Sample Output

11

Hint

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

二、思路

• 根据存在次小生成树与最小生成树只差一条边。
• 我们可以先通过kruskal求出最小生成树 O(mlogm)
• 通过这个树初始化某点到其他点的路径中最大边、次大边。 O(n^2^)
• 遍历所有未在树中的边（u–>v）， 看是否大于u到v的边的最大值， 若大于那么可以替换这条边，若不大于那就再判断是否大于次值，若大于同理进行替换。
  
• 由于这里的n过于大， 那么n^2^ 的O(mlogm + n^2^) 的复杂度就不行。 那么考虑优化一下查找u—>v的路径的最大值。可以通过lca进行优化。
• LCA入门
• 根据f[x][k] = f[f[x][k-1]][k-1]的递推。 我们可以类似求出d[x][k] = max(d[x][k - 1], d[f[x][k-1]][k - 1])
  
• 查询的时候我们是查询x–>y中路径的最大值、次大值。 那么可以在lca的查询中。查询x->lca那一段中的所有最大、次大，y到lca中所有的最大、次大， 最后从这些最大、次大里面选出最大、次大值即可。

三、代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iostream>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5, M = 3e5 + 5, INF = 0x3f3f3f3f;
struct E {
    int v, w, next;
} e[M];
struct Edge {
    int u, v, w; 
    bool st; //代表是否在树中 
    bool operator < (const Edge&o) const {return w < o.w;}
} edge[M]; 
int n, m, lg, u, v, w, len, h[N], p[N], f[N][20], d1[N][20], d2[N][20], dep[N];
void add(int u, int v, int w) {e[++len].v = v; e[len].w = w; e[len].next = h[u]; h[u] = len; }
int find(int x) {return x == p[x] ? x : (p[x] = find(p[x]));}
ll kruskal() {
    ll sum = 0;
    sort(edge + 1, edge + 1 + m);
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 1; i <= m; i++) {
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            p[fu] = fv;
            sum += w;
            edge[i].st = true;
            add(u, v, w); add(v, u, w); //构成树 
        }
    }
    return sum;
}
void bfs() {
    dep[1] = 1;
    queue<int> q; q.push(1); 
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int j = h[u]; j; j = e[j].next) {
            int v = e[j].v;
            if (dep[v]) continue;  
            dep[v] = dep[u] + 1;
            q.push(v); 
            //初始化 向上跳的点 和 路径最大、次大值
            f[v][0] = u, d1[v][0] = e[j].w, d2[v][0] = -INF; //最开始无次大值 
            for (int k = 1; k <= lg; k++) {
                int tv = f[v][k - 1];
                f[v][k] = f[tv][k - 1];
                //最大值 次大值 在4个值中寻找
                int t1 = d1[v][k - 1], t2 = d1[tv][k - 1];
                d1[v][k] = max(t1, t2);
                if (t1 == t2) d2[v][k] = max(d2[v][k - 1], d2[tv][k - 1]); 
                else if (t1 > t2) d2[v][k] = max(d2[v][k - 1], t2);
                else d2[v][k] = max(t1, d2[tv][k - 1]);
            } 
        }
    }
} 
int lca(int x, int y, int w) {
    int td[8 * lg], cnt = 0;//记录寻找lca途径中的最大、次大 
    int td1 = -INF, td2 = -INF; 
    if (dep[y] > dep[x]) swap(x, y); //x是较深的那个节点
    //1.让x y 同层
    for (int k = lg; k >= 0; k--) {
        if (dep[f[x][k]] >= dep[y]) {
            //记录中间路径最大值次大值
            td[++cnt] = d1[x][k];
            td[++cnt] = d2[x][k]; 
            x = f[x][k];
        } 
    } 
    if (x != y) {
        for (int k = lg; k >= 0; k--) {
            if (f[x][k] != f[y][k]) {
                td[++cnt] = d1[x][k]; td[++cnt] = d2[x][k]; 
                td[++cnt] = d1[y][k]; td[++cnt] = d2[y][k];
                x = f[x][k], y = f[y][k]; 
            }
        }
        //最后还要跳一层
        td[++cnt] = d1[x][0]; td[++cnt] = d2[x][0]; 
        td[++cnt] = d1[y][0]; td[++cnt] = d2[y][0]; 
    }
    //扫描td数组 求出最小最大值 
    for (int i = 1; i <= cnt; i++) {
        if (td[i] > td1) {
            td2 = td1; td1 = td[i];
        } else if (td[i] != td1 && td[i] > td2) td2 = td[i];
    } 
    if (w > td1) return td1;
    if (w > td2) return td2; //若与最大大值相等就判断是否大于次大值 
    return INF;
}
int main() {    
    scanf("%d%d", &n, &m);
    lg = int(log(n) / log(2)) + 1;//最多跳的次方 
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    //求出最小生成树
    ll sum = kruskal(), ans = 1e18; 
    bfs(); //lca初始化 
    for (int i = 1; i <= m; i++) {
        if (!edge[i].st) {
            int u = edge[i].u, v = edge[i].v, w = edge[i].w;
            ans = min(ans, sum + w - lca(u, v, w));
        }
    }
    printf("%lld", ans);
    return 0;
}