先决条件 : 掌握 最小生成树 Kruskal 算法 , 基础的 dp 能力 , 熟练掌握并深刻理解 倍增 lca

严格次小生成树

定义 :

我们定义次小生成树为 选边和最小生成树不一样的，边权总和最小的生成树
那么严格次小生成树就是边权总和严格小于最小生成树边权总和的次小生成树

求严格次小生成树的思想：

假设我们已经求得最小生成树，对这棵最小生成树，加入一条非树边肯定会形成环
根据排序原则，较小的边会优先构成一个集合，非树边不在集合中，权值就一定大于等于环上边的权值
那么对于所求的严格次小生成树，应该在环上找除了非树边外权值最大的边，去掉，更新答案

但是，如果非树边与环上权值最大边 权值相等，那么这棵次小生成树就不严格
所以，我们还要求出环上的权值次大的边，然后比较，判断，更新答案个

解法步骤：

1) Kruskal 求出最小生成树，标记已经在树上的边，对更新答案有帮助的一定是非树边

代码实现 :

//关于初始数组及字符含义：

struct rec
{
    int x,y,z,id;
}e[N];      int fa[N];
//Kruskal 求最小生成树，存边 

struct EDGE
{
    int ver,nex,edge;
}E[N<<1];   int head[N];
//邻接表 

struct DP
{
    int fa,max1,max2;
}f[N][25];  int dep[N];
//dp 倍增 

int n,m,tot,t;
ll res=0,ANS=1e16;
//res : 最小生成树边权权值总和
//ans : 严格次小生成树边权权值总和 
bool v[N];
//求非树边 

queue<int> q;

// 步骤 1) 的实现 : 

bool cmp(rec a,rec b) {return a.z<b.z;}

int get(int x) {return x==fa[x]?x:fa[x]=get(fa[x]);}

inline void kruskal()
{
    for(int i=1;i<=n;i++) fa[i]=i;

    sort(e+1,e+m+1,cmp);

    for(int i=1;i<=m;i++)
    {
        int x=get(e[i].x),y=get(e[i].y);
        if(x==y) continue;
        fa[x]=y;res+=e[i].z;v[i]=1;
        add(e[i].x,e[i].y,e[i].z); add(e[i].y,e[i].x,e[i].z);
    }
}

2) 倍增求 lca ，预处理的同时 dp 出 x 到 x 的 2 ^ i 祖先的路径上的权值最大边和次大边

我们要求的是两点间的权值最大边和次大边，等价于求两点分别到 lca 路径中权值最大的边和次大边
倍增处理 lca 时可以顺带 dp 出来

代码实现 :

// 步骤 2) 的实现 : 

inline DP adde(int far,int maxn1,int maxn2) {DP a;a.fa=far;a.max1=maxn1;a.max2=maxn2;return a;}

inline DP MAX(DP a,DP b)
//更新最大边、次大边
{
    if(a.max1>b.max1) b.max2=b.max1,b.max1=a.max1;
    if(a.max1>b.max2&&a.max1<b.max1) b.max2=a.max1;
    return b;
}

inline void bfs()
//bfs 预处理能应对更大的数据
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<=t;j++) f[i][j]=adde(-1,-1,-1);
    //初始化
    dep[1]=1;q.push(1);
    while(q.size())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=E[i].nex)
        {
            int y=E[i].ver;
            if(dep[y]) continue;
            dep[y]=dep[x]+1;
            f[y][0]=adde(x,E[i].edge,-1);
            for(int j=1;j<=t;j++)
            {
                int far=f[y][j-1].fa;
                if(far==-1) break;
                f[y][j]=MAX(f[y][j-1],f[far][j-1]);
                //自下往上更新 
            }
            q.push(y);
        }
    }
}

3) 扫描非树边，判断两点间权值最大边的权值是否等于非树边的权值，然后考虑删去那条边来跟新答案

至此，问题得以解决

代码实现 :

// 步骤 3) 的实现 :

inline DP quiry(int x,int y)
//实际上相当于求 lca
{
    DP tmp=adde(-1,-1,-1);
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=t;i>=0;i--)
        if(dep[f[x][i].fa]>=dep[y]) tmp=MAX(tmp,f[x][i]),x=f[x][i].fa;
    if(x==y) return tmp;
    for(int i=t;i>=0;i--)
        if(f[x][i].fa!=f[y][i].fa)
            tmp=MAX(tmp,MAX(f[x][i],f[y][i])),x=f[x][i].fa,y=f[y][i].fa;
    return MAX(tmp,MAX(f[x][0],f[y][0]));
}

//主函数中

    for(int i=1;i<=m;i++)
        if(!v[i])
        {
            DP tmp=quiry(e[i].x,e[i].y);
            //严格的次小生成树
            if(tmp.max1==e[i].z&&tmp.max2!=-1) ANS=min(ANS,res-tmp.max2+e[i].z);
            if(e[i].z>tmp.max1) ANS=min(ANS,res-tmp.max1+e[i].z);
        }

模板 AcWing 1151 次小生成树

https://www.acwing.com/problem/content/1153/

完整代码 :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=4e5+10;

struct rec
{
    int x,y,z,id;
}e[N];      int fa[N];

struct EDGE
{
    int ver,nex,edge;
}E[N<<1];   int head[N];

struct DP
{
    int fa,max1,max2;
}f[N][25];  int dep[N];

int n,m,tot,t;
ll res=0,ANS=1e16;
bool v[N];

queue<int> q;

inline int read()
{
    static int x;x=0;char ch;ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x;
}

bool cmp(rec a,rec b)
{
    return a.z<b.z;
}

inline void add(int x,int y,int z)
{
    E[++tot].ver=y;E[tot].edge=z;E[tot].nex=head[x];head[x]=tot;
}

int get(int x)
{
    return x==fa[x]?x:fa[x]=get(fa[x]);
}

inline DP adde(int far,int maxn1,int maxn2)
{
    DP a;a.fa=far;a.max1=maxn1;a.max2=maxn2;return a;
}

inline void kruskal()
{
    for(int i=1;i<=n;i++) fa[i]=i;

    sort(e+1,e+m+1,cmp);

    for(int i=1;i<=m;i++)
    {
        int x=get(e[i].x),y=get(e[i].y);
        if(x==y) continue;
        fa[x]=y;res+=e[i].z;v[i]=1;
        add(e[i].x,e[i].y,e[i].z); add(e[i].y,e[i].x,e[i].z);
    }
}

inline DP MAX(DP a,DP b)
{
    if(a.max1>b.max1) b.max2=b.max1,b.max1=a.max1;
    if(a.max1>b.max2&&a.max1<b.max1) b.max2=a.max1;
    return b;
}

inline void bfs()
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<=t;j++) f[i][j]=adde(-1,-1,-1);
    dep[1]=1;q.push(1);
    while(q.size())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=E[i].nex)
        {
            int y=E[i].ver;
            if(dep[y]) continue;
            dep[y]=dep[x]+1;
            f[y][0]=adde(x,E[i].edge,-1);
            for(int j=1;j<=t;j++)
            {
                int far=f[y][j-1].fa;
                if(far==-1) break;
                f[y][j]=MAX(f[y][j-1],f[far][j-1]); 
            }
            q.push(y);
        }
    }
}

inline DP quiry(int x,int y)
{
    DP tmp=adde(-1,-1,-1);
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=t;i>=0;i--)
        if(dep[f[x][i].fa]>=dep[y]) tmp=MAX(tmp,f[x][i]),x=f[x][i].fa;
    if(x==y) return tmp;
    for(int i=t;i>=0;i--)
        if(f[x][i].fa!=f[y][i].fa)
            tmp=MAX(tmp,MAX(f[x][i],f[y][i])),x=f[x][i].fa,y=f[y][i].fa;
    return MAX(tmp,MAX(f[x][0],f[y][0]));
}

int main()
{
    n=read();m=read();

    t=(int)(log(n)/log(2))+1;

    for(int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].z=read(),e[i].id=i;

    kruskal();
    bfs();

    for(int i=1;i<=m;i++)
        if(!v[i])
        {
            DP tmp=quiry(e[i].x,e[i].y);
            if(tmp.max1==e[i].z&&tmp.max2!=-1) ANS=min(ANS,res-tmp.max2+e[i].z);
            if(e[i].z>tmp.max1) ANS=min(ANS,res-tmp.max1+e[i].z);
        }

    printf("%lld",ANS);

    return 0;
}