在普通次小生成树的基础上再维护一个树上严格次大值即可。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #include<bitset> using namespace std; typedef long long LL; int n,m; int fa[110000]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int Union(int x,int y) { int fx=find(x),fy=find(y); if (fx!=fy) fa[fx]=fy; else return 0; return 1; } struct node { int x,y,z,use; }a[610000]; int cmp(node a,node b) { return a.z<b.z; } int e[210000],pre[210000],last[210000],w[210000],dep[210000],num; LL now; int mx[210000][20],f[210000][20],m2[210000][20]; int lca(int x,int y) { if (dep[x]<dep[y]) swap(x,y); int tmp=dep[x]-dep[y]; for (int i=17;i--;) if (tmp>>i&1) x=f[x][i]; if (x==y) return x; for (int i=17;i--;) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } void dfs(int x,int y,int depth,int z) { dep[x]=depth; f[x][0]=y; mx[x][0]=z; m2[x][0]=0; for (int i=1;i<=17;i++) { f[x][i]=f[f[x][i-1]][i-1],mx[x][i]=max(mx[x][i-1],mx[f[x][i-1]][i-1]); if (mx[x][i-1]<mx[f[x][i-1]][i-1]) { if (m2[f[x][i-1]][i-1]>mx[x][i-1]) m2[x][i]=m2[f[x][i-1]][i-1]; else m2[x][i]=mx[x][i-1]; } else if (mx[x][i-1]>mx[f[x][i-1]][i-1]) { if (m2[x][i-1]>mx[f[x][i-1]][i-1]) m2[x][i]=m2[x][i-1]; else m2[x][i]=mx[f[x][i-1]][i-1]; } else { if (m2[x][i-1]>m2[f[x][i-1]][i-1]) m2[x][i]=m2[x][i-1]; else m2[x][i]=m2[f[x][i-1]][i-1]; } } for (int i=last[x];i;i=pre[i]) if (e[i]!=y) dfs(e[i],x,depth+1,w[i]); } LL ans=1e18; int main() { scanf("%d %d",&n,&m); for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=m;i++) { int x,y,z; scanf("%d %d %d",&x,&y,&z); a[i]={x,y,z,0}; } sort(a+1,a+1+m,cmp); for (int i=1;i<=m;i++) { int x=a[i].x,y=a[i].y,z=a[i].z; if (find(x)!=find(y)) { now+=(LL)z; fa[find(x)]=find(y); e[++num]=y,pre[num]=last[x],last[x]=num,w[num]=z; e[++num]=x,pre[num]=last[y],last[y]=num,w[num]=z; a[i].use=1; } } dfs(1,0,0,0); for (int i=1;i<=m;i++) { if (a[i].use) continue; int x=a[i].x,y=a[i].y,z=a[i].z; int d=lca(x,y); int dx=dep[x]-dep[d],dy=dep[y]-dep[d]; int mm=0,nn=x; for (int j=0;j<=17;j++,dx>>=1) if (dx&1) { if (mm<mx[x][j]&&mx[x][j]!=z) mm=mx[x][j]; if (mm<m2[x][j]&&m2[x][j]!=z) mm=m2[x][j]; x=f[x][j]; } nn=y; for (int j=0;j<=17;j++,dy>>=1) if (dy&1) { if (mm<mx[y][j]&&mx[y][j]!=z) mm=mx[y][j]; if (mm<m2[y][j]&&m2[y][j]!=z) mm=m2[y][j]; y=f[y][j]; } ans=min(ans,now-(LL)mm+(LL)z); } cout<<ans<<endl; return 0; }