顾名思义。
生成树，边权和严格小于最小生成树
一定和最小生成树有关系。
实际上，有
结论1：严格次小生成树只在最小生成树上改动一条边
证明：
改动一条边有意义的话，必然改完这条边，总和变大。
那么这至少是严格次小生成树的最大值。再改一条也没有意义。
结论2：改动的那条边w，一定是新加入的那条边覆盖的树链的最大值或者严格次大值。
证明：
w比最大值大的话，一定扔掉这个最大值
相等的话，一定扔掉严格次大值。
如果不存在严格次大值，那么不可能。也符合“严格”的题意。
kruscal跑MST
枚举剩下没有加入的边，要求出这条链上的最大值和严格次大值
可以倍增，树剖，LCT等等。
倍增显然最优。
#include<bits/stdc++.h> #define il inline #define reg register int #define numb (ch^'0') #define int long long using namespace std; typedef long long ll; il void rd(int &x){ char ch;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=100000+5; const int M=300000+5; const ll inf=0x3f3f3f3f3f3f3f3f; int n,m; struct node{ int x,y; ll z; bool in; bool friend operator <(node a,node b){ return a.z<b.z; } }bian[M]; int ff[N]; int fin(int x){ return ff[x]==x?x:ff[x]=fin(ff[x]); } int fa[N][20],mx[N][20],cmx[N][20]; ll sum; struct edge{ int nxt,to; int val; }e[2*N]; int hd[N],cnt; void add(int x,int y,int z){ e[++cnt].nxt=hd[x]; e[cnt].to=y; e[cnt].val=z; hd[x]=cnt; } int dep[N]; ll ans; void dfs(int x,int d){ dep[x]=d; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa[x][0]) continue; fa[y][0]=x; mx[y][0]=e[i].val; cmx[y][0]=-inf; dfs(y,d+1); } } int query(int x,int y,ll z){//z is val of new edge int big=-inf; if(dep[x]<dep[y]) swap(x,y); for(reg j=19;j>=0;--j){ if(dep[fa[x][j]]>=dep[y]){ if(mx[x][j]!=z) big=max(big,mx[x][j]); else big=max(big,cmx[x][j]); x=fa[x][j]; } } if(x==y){ return z-big; } for(reg j=19;j>=0;--j){ if(fa[x][j]!=fa[y][j]){ if(mx[x][j]!=z) big=max(big,mx[x][j]); else big=max(big,cmx[x][j]); x=fa[x][j]; if(mx[y][j]!=z) big=max(big,mx[y][j]); else big=max(big,cmx[y][j]); y=fa[y][j]; } } int j=0; if(mx[x][j]!=z) big=max(big,mx[x][j]); else big=max(big,cmx[x][j]); if(mx[y][j]!=z) big=max(big,mx[y][j]); else big=max(big,cmx[y][j]); return z-big; } int main(){ rd(n);rd(m); memset(mx,-1,sizeof mx); memset(cmx,-1,sizeof cmx); int x,y,z; for(reg i=1;i<=m;++i){ rd(x);rd(y);rd(z); bian[i].x=x,bian[i].y=y;bian[i].z=z; } for(reg i=1;i<=n;++i) ff[i]=i; sort(bian+1,bian+m+1); for(reg i=1;i<=m;++i){ int x=bian[i].x,y=bian[i].y; int k1=fin(x),k2=fin(y); if(k1!=k2){ ff[k1]=k2; bian[i].in=1; sum+=bian[i].z; add(bian[i].x,bian[i].y,bian[i].z); add(bian[i].y,bian[i].x,bian[i].z); } } //cout<<" sum "<<sum<<endl; dep[0]=-1; dfs(1,1); for(reg j=1;j<=19;++j){ for(reg i=1;i<=n;++i){ fa[i][j]=fa[fa[i][j-1]][j-1]; int big=mx[fa[i][j-1]][j-1],cbig=cmx[fa[i][j-1]][j-1]; mx[i][j]=max(mx[i][j-1],big); cmx[i][j]=max(cmx[i][j-1],cbig); if(mx[i][j-1]>big) cmx[i][j]=max(cmx[i][j],big); if(mx[i][j-1]<big) cmx[i][j]=max(cmx[i][j],mx[i][j-1]); } } ans=0x3f3f3f3f3f3f3f3f; for(reg i=1;i<=m;++i){ if(!bian[i].in){ int tmp=query(bian[i].x,bian[i].y,bian[i].z); ans=min(ans,sum+tmp); } } printf("%lld",ans); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2018/12/19 14:36:23 */