莫欺少年穷，修魔之旅在这开始—>算法提高课题解

次小生成树

思路：

1. 先建立最小生成树
2. 预处理每个点之间的最大值 dist1[a][b] 和次大值 dist2[a][b]
3. 枚举所有非树边，加入一条非树边，必有环，去掉环中严格小于当前非树边的最大值，取最小值

可参考： 次小生成树

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 510, M = 10010;

int n,m;
int h[N],e[N*2],w[N*2],ne[N*2],idx;
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 find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

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

//预处理 a 和 b 两点之间的最大值和次大值
void dfs(int u,int fa,int maxd1,int maxd2,int d1[],int d2[])
{
    d1[u]=maxd1,d2[u]=maxd2;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=fa)
        {
            int td1=maxd1,td2=maxd2;
            if(w[i]>td1) td2=td1,td1=w[i];
            else if(w[i]<td1&&w[i]>td2) td2=w[i];
            dfs(j,u,td1,td2,d1,d2);
        }
    }
}

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

    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>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;
            add(a,b,w),add(b,a,w);
            sum+=w;
            edge[i].f=true;
        }
    }

    //预处理 dist1[a][b] 和 dist2[a][b]
    for(int i=1;i<=n;i++) dfs(i,-1,0,0,dist1[i],dist2[i]);

    //枚举所有非树边，加上去并去掉环中的严格小于非树边的最大值
    LL res=1e18,t;
    for(int i=0;i<m;i++)
        if(!edge[i].f)
        {
            int a=edge[i].a,b=edge[i].b,w=edge[i].w;
            if(w>dist1[a][b]) t=sum+w-dist1[a][b];
            else t=sum+w-dist2[a][b];
            res=min(res,t);
        }

    cout<<res<<endl;

    return 0;
}