概览

次小生成树 !!!

生成树权值第二小的为次小生成树。分两类：1. 严格小于，即不能数值相等 2. 允许数值相等

方法1：先求最小生成树，再枚举删去最小生成树中的边求解。 kruskal(主要是排序) O(mlogm), O(nm)
方法2： 先求最小生成树，然后依次枚举非树边，然后将该边加入树中。同时从树中去掉一条边，使得最终仍为一棵树 O(m + n^2 + mlogm) 看代码

证明，通过kruskal的证明过程思考，想象为连接两个连通分支。

mlogm 排序
求树上任意两点的极值(最大的边) O(n^2)
m 删树边，替换非树边操作

题解

方法2, 求解过程

1. 求最小生成树，标记每条边是树边还是非树边。同时把最小生成树建立出来
2. 预处理任意两点间的边权最大值dist[a][b]
3. 依次枚举所有非树边. min(sum+w - dist[a][b]) w > dist[a][b]. 如果大于进行更新

   每个非树边替换后一定对吗？. 更新时，去掉的是与a相邻的树边？还是与b相邻的树边?
   问题回答！ 对的！都不是，替换的是a,b之间的极值边，即a,b通路上权值最大的边。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long LL;
const int N = 510, M = 10010;

int n, m;
struct Edge {
    int a, b, w;
    bool f;
    bool operator< (const Edge &t) const {
        return w < t.w;
    }
} edge[M];
int p[N];
int dist1[N][N], dist2[N][N];
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;

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

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

void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[]) { // fa, -1, 避免往回搜
    d1[u] = maxd1, d2[u] = maxd2; // d[a][u] 需要弄明白，其实是最小生成树中 a->v1->...->u. 这条通路中，权值最大的边。
    // 非树边a->u替换的想法其实关键就是。 就a->v1->...->u->a.  将a->u. 替换第二权值的边，使得a,u仍然连通
    // 所以这必然需要处理第二小的边权才是。
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j != fa) { // 这里保存第1小，第2小，..., 实际的做法是一样的
            int td1 = maxd1, td2 = maxd2;
            if (w[i] > td1) td2 = td1, td1 = w[i];
            else if (w[i] > td2) td2 = w[i];
            dfs(j, u, td1, td2, d1, d2); 
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edge[i] = {a, b, w};
    }

    sort(edge, edge + m);
    for (int i = 1; i <= n; i ++) p[i] = i;

    LL sum = 0;
    for (int i = 0; i < m; i ++) {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            p[pa] = pb;
            sum += w;
            add(a, b, w), add(b, a, w);
            edge[i].f = true;
        }
    }

    // 暴力枚举每个点到其他点的最大值
    for (int i = 1; i <= n; i ++) dfs(i, -1, 0, 0, dist1[i], dist2[i]); 

    LL res = 1e18;
    for (int i = 0; i < m; i ++)
        if (!edge[i].f) {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            LL t;
            if (w > dist1[a][b]) t = sum + w - dist1[a][b];
            else if (w > dist2[a][b]) t = sum + w - dist2[a][b];
            res = min(res, t);
        }

    printf("%lld\n", res);
    return 0;
}