维护环内最大值与严格次大值

与未放入最小生成树的边枚举加入

#include
     
      #define re return#define dec(i,l,r) for(ll i=l;i>=r;--i)#define inc(i,l,r) for(ll i=l;i<=r;++i)typedef long long ll;using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=100005,maxm=300005;ll n,m,k=1,hd[maxn],deep[maxn];ll max1[maxn][21],max2[maxn][21],fa[maxn][21];ll vis[maxm],f[maxn];ll sum,ans=999999999999999999;struct node{    ll fr,to,nt,val;    bool operator<(node p)const     {        re val
       
        max1[fa[x][i]][i])        {            max1[x][i+1]=max1[x][i];            max2[x][i+1]=max(max1[fa[x][i]][i],max2[x][i]);        }        else         {            max1[x][i+1]=max1[fa[x][i]][i];            max2[x][i+1]=max(max1[x][i],max2[fa[x][i]][i]);        }        }         for(ll i=hd[x];i;i=e1[i].nt)    {        ll v=e1[i].to;        if(v==fa[x][0])continue;        fa[v][0]=x;        max1[v][0]=e1[i].val;        max2[v][0]=-2147483647;        dfs(v);    }}inline ll find(ll x){    re x==f[x]?x:f[x]=find(f[x]);}int main(){    //    freopen("in.txt","r",stdin);freopen("tree8.in","r",stdin);        ll x,y,z;         rd(n),rd(m);    inc(i,1,n)f[i]=i;        inc(i,1,m)    {        rd(x),rd(y),rd(z);        e[i]=(node){x,y,0,z};    }        sort(e+1,e+m+1);        k=0;    ll cnt=0;    inc(i,1,m)    {        x=find(e[i].to),y=find(e[i].fr);        if(x!=y)        {            add1(e[i].to,e[i].fr,e[i].val);            sum+=e[i].val;             vis[i]=1;            f[x]=y;            ++cnt;            if(cnt==n-1)break;        }    }        dfs(1);        inc(j,1,m)    if(!vis[j])    {        x=e[j].to;y=e[j].fr;//--------------------------------------------------------------------------------                ll d1=0,d2=0;        if(deep[x]
        
         =deep[y])        {            if(max1[x][i]>d1)            {                d2=max(d1,max2[x][i]);                d1=max1[x][i];            }            else if(max1[x][i]!=d1)                 d2=max(d2,max1[x][i]);                        x=fa[x][i];        }        if(x!=y)        {            dec(i,20,0)            if(fa[x][i]!=fa[y][i])            {                if(max1[x][i]>d1)                {                    d2=max(d1,max2[x][i]);                    d1=max1[x][i];                }                else if(max1[x][i]!=d1)                     d2=max(d2,max1[x][i]);                                     if(max1[y][i]>d1)                {                    d2=max(d1,max2[y][i]);                    d1=max1[y][i];                }                else if(max1[y][i]!=d1)                     d2=max(d2,max1[y][i]);                x=fa[x][i];y=fa[y][i];            }            if(max1[x][0]>d1)            {                d2=d1;                d1=max1[x][0];             }             else if(max1[x][0]!=d1)                d2=max(d2,max1[x][0]);            if(max1[y][0]>d1)            {                d2=d1;                d1=max1[y][0];             }             else if(max1[y][0]!=d1)                d2=max(d2,max1[y][0]);                    } //-----------------------------------------------------------------------------------------------------                if(d1==e[j].val)ans=min(ans,sum+e[j].val-d2);        else ans=min(ans,sum+e[j].val-d1);    }        printf("%lld",ans);     re 0;}