严格次小生成树 ：边权和大于最小生成树
非严格次小生成树 ：边权和大于等于最小生成树
-----------严格次小生成树----------
-时间复杂度O(mlog(mn))
首先求最小生成树，O(mlogm)
那么次小生成树就是将最小生成树上的一条边换掉
-正确性
每换掉一条边，边权和肯定变大
如果存在改变两条边的最小生成树是严格次小生成树的话，那么只改一条边时边权和肯定小于 改变两条边
所以选择换掉的边是使边权和增加最小的边
每次换掉一条边时
被换掉的边与即将换上的边构成一个环，我们要从这个环上删去一条边，被删去的边在 即将换上的边 的两个节点树上路径里
被换掉的边一定是可以被换掉的边中边权最大的
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct ll{int x,y,len,vis;} s[300020]; int head[100005],nxt[200005],to[200005],val[300005],cnt;//val数组开2*10^5+5就会RE的玄学问题 int n,m,f[100005][25],maxv[100005][25],max2[100005][25],dep[100005],fa[100005]; void add(int x,int y,int v) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=v; } bool cmp(ll a,ll b){return a.len<b.len;} long long ans; int getfa(int x){return (fa[x]==x)?x:(fa[x]=getfa(fa[x]));} void dfs(int x,int fa)//建树 { f[x][0]=fa; for(int i=head[x]; i; i=nxt[i]) { if(to[i]==fa) continue; dep[to[i]]=dep[x]+1; maxv[to[i]][0]=val[i]; max2[to[i]][0]=-2e9;//防止自环 dfs(to[i],x); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=24; i>=0; i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i]; if(x==y) return x; for(int i=24; i>=0; i--) if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } return f[x][0]; } int qiumax(int x,int y,int vall) { int maxx=-2e9; for(int i=24;i>=0&&x!=y;i--) { if(dep[f[x][i]]>=dep[y]) { if(maxv[x][i]!=vall) maxx=max(maxx,maxv[x][i]); else maxx=max(maxx,max2[x][i]); x=f[x][i]; } } return maxx; } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].len); s[i].vis=0; fa[s[i].x]=s[i].x; fa[s[i].y]=s[i].y; } int k=0; sort(s+1,s+m+1,cmp); for(int i=1; i<=m; i++)//求最小生成树 { int fax=getfa(s[i].x),fay=getfa(s[i].y); if(fax!=fay) { ans+=(long long)s[i].len; fa[fax]=fay; s[i].vis=1; k++; add(s[i].x,s[i].y,s[i].len); add(s[i].y,s[i].x,s[i].len); if(k==n-1) break; } } dep[1]=1; f[1][0]=-2e9; dfs(1,-1); for(int i=1; i<=24; i++) //LCA预处理 for(int j=1; j<=n; j++) { //从j向上走2^i步过程中最长边与次长边一定从maxv[j][i-1],maxv[f[j][i-1]][i-1]与 max2[j][i-1],max2[f[j][i-1]][i-1]中诞生 f[j][i]=f[f[j][i-1]][i-1]; maxv[j][i]=max(maxv[j][i-1],maxv[f[j][i-1]][i-1]); //从j向上走2^i步过程中最长边 max2[j][i]=max(max2[j][i-1],max2[f[j][i-1]][i-1]); //次长边 if(maxv[j][i-1]>maxv[f[j][i-1]][i-1]) max2[j][i]=max(max2[j][i],maxv[f[j][i-1]][i-1]); else if(maxv[j][i-1]<maxv[f[j][i-1]][i-1]) max2[j][i]=max(maxv[j][i-1],max2[j][i]); } long long sum=2e16; for(int i=1; i<=m; i++) { if(!s[i].vis) { int lcca=lca(s[i].x,s[i].y); int mxx1=qiumax(s[i].x,lcca,s[i].len); int mxx2=qiumax(s[i].y,lcca,s[i].len); sum=min(sum,ans+(long long)s[i].len-(long long)max(mxx1,mxx2)); } } printf("%lld",sum); return 0; }