算法1

/
* 使用克鲁斯卡尔算法先生成最小生成树
* 由定理证明可知 次小生成树最多只用换掉最小生成树中的一条边（本题要求绝对次小生成树 我们选出的非树边要比换掉的树边至少大1）
* 在任意添加一条边之后 如A-B 那么A-B会形成一个环路 那么由于生成次小生成树 则需要换掉环路中值最大的边
* 对于重边的情况使用上条策略仍然成立
* 由于需要生成绝对次小生成树 那么当最大值与我们挑出的非树边相等时那么 我们需要换掉树中的次小边才能保证此次换边生成的是次小生成树
* 深度优先搜索找出树中A 到 B 的最大边与最小边即可
* /

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=510,M=1e4+10,E=M*2;
int n,m;
int h[N],e[E],ne[E],w[E],idx=0;
int p[N];
struct link{
    int a,b,c;
    bool operator< (const link &w) const{
        return c<w.c;
    }
}edge[M];
queue<link> q;
int dist[N][N][2];
bool st[N];
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(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

void dfs(int x,int u,int val){
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(st[j]==true) continue;
        if(w[i]>val){
            dist[x][j][0]=w[i];//更新最大值
            dist[x][j][1]=val;//更新次大值
        }else if(w[i]==val){
            dist[x][j][0]=val;
            dist[x][j][1]=dist[x][u][1];//此时次大值则为父节点的次大值
        }else if(w[i]<val){
            dist[x][j][0]=val;
            dist[x][j][1]=max(dist[x][u][1],w[i]);//此时次大值为父节点的次大值与当前加入边的次大值的最大值
        }
        dfs(x,j,dist[x][j][0]);
    }
}
int main(){
    long long val=0;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edge[i]={a,b,c};
    }
    sort(edge,edge+m);
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++){
        int a=edge[i].a,b=edge[i].b,c=edge[i].c;
        int a1=find(a),b1=find(b);
        if(a1==b1) {
            q.push({a,b,c});
            continue;
        }
        p[a1]=b1;
        val+=c;
        add(a,b,c),add(b,a,c);
    }
    for(int i=1;i<=n;i++)
    {
     memset(st,0,sizeof st);
     dfs(i,i,0);
    }
    int res=0x3f3f3f3f;
    while(q.size()){
        auto t=q.front();
        q.pop();
        int a=t.a,b=t.b,c=t.c;
        if(c>dist[a][b][0]){
            res=min(res,c-dist[a][b][0]);
        }else if(c==dist[a][b][0]){
            res=min(res,c-dist[a][b][1]);
        }
    }
    cout<<val+res;
}