题目描述

小$C$最近学了很多最小生成树的算法,$Prime$算法、$Kruskal$算法、消圈算法等等。

正当小$C$洋洋得意之时,小$P$又来泼小$C$冷水了。

小$P$说,让小$C$求出一个无向图的次小生成树,而且还得是严格次小的,也就是说:

如果最小生成树选择的边集是$E_M$,严格次小生成树选择的边集是$E_S$,那么需要满足:

($value(e)$表示边$e$的权值)$\sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)$。

这下小$C$蒙了,他找到了你,希望你帮他解决这个问题。

输入格式

第一行包含两个整数$N$和$M$,表示无向图的点数与边数。

接下来$M$行,每行$3$个数$x\ \ y\ \ z$表示,点$x$和点$y$之间有一条边,边的权值为$z$。

输出格式

包含一行,仅一个数,表示严格次小生成树的边权和。
(数据保证必定存在严格次小生成树)

数据范围

数据中无向图无自环;
$50\%$的数据$N≤2000\ M≤3000$;
$80\%$的数据$N≤50000\ M≤100000$;
$100\%$的数据$N≤100000\ M≤300000$;
边权值非负且不超过$10^9$ 。

菜鸡的咆哮

引理

有至少一个(严格)次小生成树,和最小生成树之间只有一条边的差异。

于是我们可以先跑一个$MST$,枚举每条非树边。

考虑用其代替原树加边后形成的环中最大的那条边。

这样我们可以求出非严格次大生成树,即换了边但边权为减小。

为了保证加入的边与断开的边不相等从而满足严格次大,我们还要维护每条链的严格次大边权。

如果加入的边等于最大边,我们就断开次大边。

最大边和次大边的维护可以用倍增来完成

我们令$edge\_st[x][i],edge\_nd[x][i]$分别表示$x$到其$2^i$辈祖先节点链上的最大与此大边权。

显然$edge\_st[x][i]=max(edge\_st[x][i-1],edge\_st[f[x][i-1]][i-1])$

次大边权的处理部分要讨论一下:

如果$edge\_st[x][i-1]=edge\_st[f[x][i-1]][i-1]]$,

则$edge\_nd[x][i]=max(edge\_nd[x][i-1],edge\_nd[f[x][i-1]][i-1])$。

反之两段中较小的最大边可能是当前段的次大边。

$edge\_nd[x][i]=max(edge\_nd[x][i],min(edge\_st[x][i-1],edge\_st[f[x][i-1]][i-1]))$

查询时$x,y$链上要删去的边为:

$$ max([x,LCA(x,y)]上严格小于加边的最大边,[y,LCA(x,y)]上严格小于加边的最大边) $$

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define maxn 300005
using namespace std;
inline int read(){
    char ch=getchar();int s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-48;ch=getchar();}
    return s*w;
}
int n,m; 
struct data1{
    int a,b,p;
}tree[maxn];
bool cmp(data1 x,data1 y){return x.p<y.p;}
struct data2{
    int to;
    int p;
    int nextt;
}line[maxn];
int tail;
int first[maxn];
void add(int x,int y,int w){
    tail++;
    line[tail].to=y;
    line[tail].p=w;
    line[tail].nextt=first[x];
    first[x]=tail;
}
//-----------------------------------------
int fa[maxn];
int dofind(int x){
    if(fa[x]==x) return x;
    return fa[x]=dofind(fa[x]);
}
void dounion(int x,int y){
    fa[dofind(x)]=dofind(y);
}
ll sum;
int vis[maxn];
void Kruskal(){
    sort(tree+1,tree+1+m,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    int cnt=0;
    for(int i=1;i<=m;i++){
        int x=tree[i].a;
        int y=tree[i].b;
        if(dofind(x)!=dofind(y)){
            dounion(x,y);cnt++;
            add(x,y,tree[i].p);
            add(y,x,tree[i].p);
            sum+=tree[i].p;
            vis[i]=1;
        }
        if(cnt==n-1) return;
    }
}
//--------------------------------------------
int dep[maxn]; 
int f[maxn][25];
int edge_st[maxn][25];
int edge_nd[maxn][25];
void dfs(int x,int fa,int fa_edge){
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    edge_st[x][0]=fa_edge;
    edge_nd[x][0]=-0x3f3f3f3f;
    for(int i=1;i<=20;i++){
        f[x][i]=f[f[x][i-1]][i-1];
        edge_st[x][i]=max(edge_st[x][i-1],edge_st[f[x][i-1]][i-1]);
        edge_nd[x][i]=max(edge_nd[x][i-1],edge_nd[f[x][i-1]][i-1]);
        if(edge_st[x][i-1]!=edge_st[f[x][i-1]][i-1]){
            edge_nd[x][i]=max(edge_nd[x][i],min(edge_st[x][i-1],edge_st[f[x][i-1]][i-1]));
        }
    }
    for(int i=first[x];i;i=line[i].nextt){
        int y=line[i].to;
        int w=line[i].p;
        if(y==fa) continue;
        dfs(y,x,w);
    }
}
int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i]; y=f[y][i];
        }
    }    
    return f[x][0];
}
int ask_max(int x,int y,int z){
    int ans=-0x3f3f3f3f;
    for(int i=20;i>=0;i--){
        if(dep[f[x][i]]>=dep[y]){
            if(z!=edge_st[x][i]) ans=max(ans,edge_st[x][i]);
            else ans=max(ans,edge_nd[x][i]);
            x=f[x][i];
        }        
    }
    return ans;
}
//--------------------------------------------
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        tree[i].a=read();
        tree[i].b=read();
        tree[i].p=read();
    }
    Kruskal();
    dep[1]=1;
    dfs(1,0,0);
    ll ans=inf;
    for(int i=1;i<=m;i++){
        if(vis[i]) continue;
        int x=tree[i].a;
        int y=tree[i].b;
        int w=tree[i].p;
        int lca=LCA(x,y);
        int maxx=ask_max(x,lca,w);
        int maxy=ask_max(y,lca,w);
        ans=min(ans,sum+w-max(maxx,maxy));
    }
    printf("%lld\n",ans);
    return 0;
}