这个的INF必须得开大 最后找了一篇题解的INF复制上来
最小生成树和严格次小的区别？
用非树边替换最小生成树的一条边
枚举每一条非树边找两顶点树链上的最大边（如果最大边与非树边边权相同则找次大边）
然后更新最小增量 最大边和次大边可以通过树上倍增求出
#include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<stack> #include<algorithm> using namespace std; #define ll long long #define rg register const int N=100000+5,M=500000+5,inf=0x3f3f3f3f; #define INF 2147483647000000; int n,m; ll sum=0ll,ans=INF; ll p[N][25],mx[N][25],cm[N][25],dep[N]; bool used[M]; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } ll head[N],tot=0; struct edge{ll v,nxt,w;}e[M<<1]; void add(ll u,ll v,ll w){ e[++tot]=(edge){v,head[u],w};head[u]=tot; } int f[N]; struct node{ int u,v,w; // bool operator<(const edge&A)const{return w<A.w;} }nd[M]; bool cmp(node a,node b){return a.w<b.w;}; int find(int x){return f[x]==x?x:f[x]=find(f[x]);} void kruskal(){ for(int i=1;i<=n;++i) f[i]=i; int cnt=0; for(int i=1,u,v,w;i<=m&&cnt<n;++i){ u=nd[i].u,v=nd[i].v,w=nd[i].w; if(find(u)!=find(v)){ f[f[u]]=f[v]; sum+=nd[i].w,++cnt,used[i]=1; add(u,v,w),add(v,u,w); } } } void dfs(ll u,ll fa){ p[u][0]=fa; dep[u]=dep[fa]+1ll; cm[u][0]=-INF; for(ll i=head[u],v;i;i=e[i].nxt){ v=e[i].v; if(v==fa) continue; mx[v][0]=e[i].w; dfs(v,u); } } void doubling(){ for(int i=1;i<=20;++i) for(int j=1;j<=n;++j){ p[j][i]=p[p[j][i-1]][i-1]; mx[j][i]=max(mx[j][i-1],mx[p[j][i-1]][i-1]); cm[j][i]=max(cm[j][i-1],cm[p[j][i-1]][i-1]); if(mx[j][i-1]>mx[p[j][i-1]][i-1]) cm[j][i]=max(cm[j][i],mx[p[j][i-1]][i-1]); else if(mx[j][i-1]<mx[p[j][i-1]][i-1]) cm[j][i]=max(cm[j][i],mx[j][i-1]); } } ll LCA(ll a,ll b){ if(dep[a]>dep[b]) swap(a,b); for(int i=20;i>=0;--i){ if(dep[p[b][i]]<dep[a]) continue; b=p[b][i]; } if(a==b) return a; for(int i=20;i>=0;--i){ if(p[a][i]==p[b][i]) continue; a=p[a][i],b=p[b][i]; } return p[a][0]; } ll qmax(ll u,ll v,ll mxx){ ll re=-INF; for(int i=20;i>=0;--i) if(dep[p[u][i]]>=dep[v]){ if(mxx!=mx[u][i]) re=max(re,mx[u][i]); else re=max(re,cm[u][i]); u=p[u][i]; } return re; } int main(){ // freopen("in.txt","r",stdin); memset(used,0,sizeof(used)); rd(n),rd(m); ll u,v,w; for(int i=1;i<=m;++i){ rd(u),rd(v),rd(w); nd[i]=(node){u,v,w}; } sort(nd+1,nd+1+m,cmp); kruskal();dep[0]=0; dfs(1,0);doubling(); for(rg int i=1;i<=m;++i) if(!used[i]){ ll u=nd[i].u,v=nd[i].v,w=nd[i].w; ll lca=LCA(u,v); ll mxu=qmax(u,lca,w),mxv=qmax(v,lca,w); ans=min(ans,sum-max(mxu,mxv)+w); } printf("%lld",ans); return 0; }