$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

LCA倍增 + BFS预处理 + Kruskal

思路：

1. 先计算最小生成树的权值之和
2. 建立最小生成树
3. bfs 预处理每个点的深度，每个点跳 2 ^ k 步后的点，最大距离和次大距离
4. 先将其中一个点跳到和另一个点同一高度，并把最大距离和次大距离放入 distacne 数组
5. 再两个点一起跳到最小公共祖先的下面一层，并把最大距离和次大距离放入 distacne 数组
6. 遍历 distance 数组，选出最大值和次大值，最后返回差值

可参考： 秘密的牛奶运输

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010, M = 600010, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int depth[N], fa[N][17], d1[N][17], d2[N][17];
int p[N];

struct Edge {
    int a, b, w;
    bool used;

    bool operator<(const Edge &t) const {
        return w < t.w;
    }
} edge[M];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

//计算最小生成树的权值之和
LL kruskal() {
    sort(edge, edge + m);

    for (int i = 1; i <= n; i++) p[i] = i;

    LL res = 0;
    for (int i = 0; i < m; i++) {
        int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;
        if (a != b) {
            p[a] = b;
            res += w;
            edge[i].used = true;
        }
    }

    return res;
}

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

//建立最小生成树
void build() {
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i++)
        if (edge[i].used) {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            add(a, b, w), add(b, a, w);
        }
}

void bfs() {
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;

    queue<int> q;
    q.push(1);

    while (q.size()) {
        auto t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                //更新深度
                depth[j] = depth[t] + 1;
                q.push(j);

                //更新该点跳 2 ^ k 步后是什么点，以及最大距离和次大距离
                fa[j][0] = t;
                d1[j][0] = w[i], d2[j][0] = -INF;
                for (int k = 1; k <= 16; k++) {
                    int anc = fa[j][k - 1];
                    fa[j][k] = fa[anc][k - 1];

                    int distance[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
                    d1[j][k] = d2[j][k] = -INF;
                    for (int u = 0; u < 4; u++) {
                        int d = distance[u];
                        if (d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;
                        else if (d != d1[j][k] && d > d2[j][k]) d2[j][k] = d;
                    }
                }
            }
        }
    }
}

LL lca(int a, int b, int w) {
    if (depth[a] < depth[b]) swap(a, b);

    //到达同一深度，并把所有距离加入distance数组
    static int distance[100];
    int cnt = 0;
    for (int k = 16; k >= 0; k--)
        if (depth[fa[a][k]] >= depth[b]) {
            distance[cnt++] = d1[a][k];
            distance[cnt++] = d2[a][k];
            a = fa[a][k];
        }

    //到达最近公共祖先，并把所有距离加入distance数组
    if (a != b) {
        for (int k = 16; k >= 0; k--)
            if (fa[a][k] != fa[b][k]) {
                distance[cnt++] = d1[a][k];
                distance[cnt++] = d2[a][k];
                distance[cnt++] = d1[b][k];
                distance[cnt++] = d2[b][k];
                a = fa[a][k];
                b = fa[b][k];
            }

        distance[cnt++] = d1[a][0];
        distance[cnt++] = d1[b][0];
    }

    //枚举 distance 数组，选出最大距离 dist1 和次大距离 dist2
    int dist1 = -INF, dist2 = -INF;
    for (int i = 0; i < cnt; i++) {
        if (distance[i] > dist1) dist2 = dist1, dist1 = distance[i];
        else if (distance[i] != dist1 && distance[i] > dist2) dist2 = distance[i];
    }

    //返回差值
    if (w > dist1) return w - dist1;
    else if (w > dist2) return w - dist2;
    else return INF;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {a, b, c};
    }

    //最小生成树的权值之和
    LL sum = kruskal();

    //建立最小生成树
    build();

    //预处理每个点的深度，每个点跳 2 ^ k 步的后的点，最大距离和次大距离
    bfs();

    //枚举所有的非树边
    LL res = 1e18;
    for (int i = 0; i < m; i++)
        if (!edge[i].used) {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;

            //去掉一条环中严格小于当前非树边的最大树边
            res = min(res, sum + lca(a, b, w));
        }

    cout << res << endl;

    return 0;
}