次小生成树问题
次小生成树是这样的一个问题：给定一个图，求它生成树中第二小的。
其中生成树的大小为生成树中边权之和。
这个问题有非严格次小和严格次小两种。
算法1
暴力枚举生成树然后排序取第二小。
算法2
可以证明，一定可以在最小生成树中仅替换一条边得到次小生成树。
构造最小生成树，枚举其中每条边，删掉这条边，再在其它边中选最小的可以加进来的一条加进来。
得到的新生成树中取最小值。
那么用kruskal特别方便。
时间复杂度\(O(nm)\)
当然对于严格次小，选的边一定要比这条边大。
算法3
kruskal构造最小生成树。
枚举每条不在生成树上的边\(<u,v>\)，把它加上去后就会出现一个环。
那么在原树上找到\(<u,v>\)之间的路径，删掉最大边，然后加上这条边即可得到新的生成树。
这些里面取最小值即可。
最大边可以通过倍增找lca计算出来。
时间复杂度\(O(m\log n)\)
对于严格次小生成树，如果最大边和这条边边权一样，就要取严格次大值。
严格次大值也可以倍增计算。
这是洛谷4180 【模板】严格次小生成树 的代码。
/*
Author: CNYALI_LK
LANG: C++
PROG: 4180.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
putchar(end);
}
struct edge{
ll u,v,w;
};
edge e[333333];
ll fa[102424],use[333333];
ll beg[102424],to[204848],lst[204848],w[204848],dis[102424],en;
ll f[102424][20],mx1[102424][20],mx2[102424][20];
ll e_cmp(edge a,edge b){
return a.w<b.w;
}
ll find(ll x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void add(ll u,ll v,ll wa){
to[++en]=v;
lst[en]=beg[u];
beg[u]=en;
w[en]=wa;
}
void dfs(ll x,ll fa){
f[x][0]=fa;
dis[x]=dis[fa]+1;
for(ll i=beg[x];i;i=lst[i])if(to[i]!=fa){
dfs(to[i],x);
}
else mx1[x][0]=w[i];
}
void upd(ll &mx1,ll &mx2,ll mxx1,ll mxx2){
ll nm=max(mx1,mxx1),inm=0;
if(mx1==nm)chkmax(inm,mx2);
else chkmax(inm,mx1);
if(mxx1==nm)chkmax(inm,mxx2);
else chkmax(inm,mxx1);
mx1=nm;
mx2=inm;
}
void build(ll n,ll t){
for(ll j=1;j<=t;++j)for(ll i=1;i<=n;++i){
f[i][j]=f[f[i][j-1]][j-1];
mx1[i][j]=mx1[i][j-1];
mx2[i][j]=mx2[i][j-1];
upd(mx1[i][j],mx2[i][j],mx1[f[i][j-1]][j-1],mx2[f[i][j-1]][j-1]);
}
}
ll _lca(edge e){
ll u=e.u,v=e.v,w=e.w,max1=0,max2=0;
if(dis[u]<dis[v])swap(u,v);
for(ll i=18;~i;--i){
if(dis[u]-(1<<i)>=dis[v]){
upd(max1,max2,mx1[u][i],mx2[u][i]);
u=f[u][i];
}
}
for(ll i=18;~i;--i){
if(f[u][i]!=f[v][i]){
upd(max1,max2,mx1[u][i],mx2[u][i]);
upd(max1,max2,mx1[v][i],mx2[v][i]);
u=f[u][i];
v=f[v][i];
}
}
if(u!=v){
ll i=0;
upd(max1,max2,mx1[u][i],mx2[u][i]);
upd(max1,max2,mx1[v][i],mx2[v][i]);
u=f[u][i];
v=f[v][i];
}
if(max1==w)if(max2)return w-max2;else return 0x3f3f3f3f3f3f3f3f;
else return w-max1;
}
int main(){
#ifdef cnyali_lk
freopen("4180.in","r",stdin);
freopen("4180.out","w",stdout);
#endif
ll n,m;
n=read();m=read();
for(ll i=1;i<=m;++i){
e[i].u=read();
e[i].v=read();
e[i].w=read();
}
sort(e+1,e+m+1,e_cmp);
for(ll i=1;i<=n;++i)fa[i]=i;
ll q=n;
ll sum=0,ans=0x3f3f3f3f3f3f3f3f;
for(ll i=1;q>1;++i)if(find(e[i].u)!=find(e[i].v)){
add(e[i].v,e[i].u,e[i].w);
add(e[i].u,e[i].v,e[i].w);
sum+=e[i].w;
fa[find(e[i].u)]=find(e[i].v);
use[i]=1;
--q;
}
dfs(1,0);
build(n,18);
for(ll i=1;i<=m;++i)if(!use[i]){
chkmin(ans,sum+_lca(e[i]));
}
printf("%lld\n",ans);
return 0;
}