题目描述

注释。

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
using namespace std;

typedef long long LL;

const int N=1e5+10,M=3e5+10,INF=0x3f3f3f3f;

/*
    把非树边的每一条边加入到最小生成树中，形成一个环，在环中任意去除一条边，则可得到新生成树。为求得次小生成树，需要保存a到b的树中路径中最大值和次大值。
    如果加入的边比d1大，则则次小生成树为sum+w-d1；如果加入的边==d1，则次小生成树为sum+w-d2;
    以上可以得到其中一个候选答案，分别枚举每一条非树边，即可得到全局最优解。

    题目的核心问题转化成，如何求出任意路径中的最大边和严格次大边。

    F表示法和之前定义相同。d1[x][k]表示从x到F[x][k]之间的最大边，d2[x][k]表示严格次大边。
    G[x,k,0]=max(G[x,k-1,0],G[F[x,k-1],k-1,0]);
    严格次大边： 如果两部分的最大边相同，取次大边大的。
                 如果不同，则取较小的最大边，和最大边较大的严格次大边之间的 max；

    关于初值：G[x,0,0]=edge(x,father(x))
              G[x,0,1]= -INF 表示不存在次大值

    在LCA的同时更新d1和d2即可。
*/



struct Edge
{
    int a,b,w;
    bool used;
    bool operator < (const Edge &t) const
    {
        return w<t.w;
    }
}edge[M];

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

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,ne[idx]=h[a],w[idx]=c,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,c=edge[i].w;
            add(a,b,c),add(b,a,c);
        }
    }
}

void bfs()
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    q[0] = 1;
    int hh = 0, tt = 0;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        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[ ++ tt] = j;
                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];         //这里采用y总的更新方式，四个数值中的最大值和次大值。
                    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;
                    }
                }
            }
        }
    }
}


int lca(int a,int b,int w)
{
    static int distance[2*N];
    int cnt=0;
    if(depth[b] > depth[a]) swap(a,b);

    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];
        }
    }
    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];
    }

    int dist1=-INF,dist2=-INF;
    for(int i=0;i<cnt;i++)
    {
        int d=distance[i];
        if(d>dist1) dist2=dist1,dist1=d;
        if(d != dist1 && d > dist2) dist2=d;
    }

    if(w>dist1) return w-dist1;
    if(w>dist2) return w-dist2;

    return INF;
}



int main()
{

    scanf("%d %d",&n,&m);

    for(int i=0;i<=n;i++) p[i]=i;       //先跑一遍Kruskal，得到最小生成树，求得sum和树本身。

    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);

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

    build();        //建图
    bfs();          //预处理

    LL res=1e18;

    for(int i=0;i<m;i++)
    {
        if(!edge[i].used)       //更新每一条非树边
        {
            int a=edge[i].a,b=edge[i].b,c=edge[i].w;
            res=min(res,sum+lca(a,b,c));
        }
    }
    //cout<<sum<<endl;
    cout<<res<<endl;


    return 0;
}