一、总体思路
首先,我这一题的思路是倍增LCA+Kruskal
关键在于次小生成树怎么求：
问自己一些问题
-
怎么求不严格次小生成树
-
不严格次小生成树为什么不严格
方法每次选择U—V之间的边，前提是最小生成树上不存在的边，添边之后删去较短边，使用LCA找到祖先，删边，这里保证次小生成树的是？只要添得边不是U-V在树上最小距离即可。
模板
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
typedef long long ll;
using namespace std;
const int M=1e5+100;
ll n,m,res,ans=0x3f3f3f3f,mx;
int f[M],fa[25][M],dep[M];
ll d[2][25][M];
bool used[3*M],vis[M];
vector<int> a[M];
struct Edge{
int from, to;
ll val;
bool operator < (const Edge y){
return val < y.val;
}
}e[3*M];
int F(int x){
if(f[x]==x) return x;
return f[x]=F(f[x]);
}
void kruskal(){ //kruskal 算最大生成树（已保证任意两点之间最小限重最优）
sort(e,e+m); int lef=n-1;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=0;i<m && lef;++i){
int x=F(e[i].from),y=F(e[i].to);
if(x!=y){
f[x]=y; res+=e[i].val;
used[i]=1; --lef;
mx=max(mx , e[i].val);
}
}
}
void dfs(int x){ //深搜建树（可能不止一棵，因为数据未保证是连通图）
vis[x]=true;
for(int i=1;i<=23;++i){
fa[i][x]=fa[i-1][fa[i-1][x]];
ll t1=d[0][i-1][x], t2=d[0][i-1][fa[i-1][x]];
d[0][i][x]=max(t1 , t2);
d[1][i][x]=max(d[1][i-1][x] , d[1][i-1][fa[i-1][x]]);
if(t1!=t2) d[1][i][x]=max(d[1][i][x] , min(t1 , t2));
}
for(int i=0;i<a[x].size();++i){
int t=e[a[x][i]].to+e[a[x][i]].from-x;
if(vis[t]) continue; //vis为1表示是父节点
dep[t]=dep[x]+1; fa[0][t]=x;
d[0][0][t]=e[a[x][i]].val; dfs(t);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])
swap(u,v);
if(dep[u]!=dep[v]){ //将深度做相等
for(int i=23,h=dep[u]-dep[v];i>=0;--i)
if(h&(1<<i)) u=fa[i][u];
}
if(u==v) return u; //如果已经在一个节点上就直接返回
for(int i=23;i>=0;--i) if(fa[i][u]!=fa[i][v])
u=fa[i][u] , v=fa[i][v];
return fa[0][u];
}
ll get(int u,int v,int c){
int fht=lca(u,v);
ll m1=0,m2=0;
for(int i=23,h1=dep[u]-dep[fht],h2=dep[v]-dep[fht];i>=0;--i){
if(h1&(1<<i)){
if(d[0][i][u]>m1) m2=m1,m1=d[0][i][u];
else if(d[0][i][u]>m2) m2=d[0][i][u];
else m2=max(m2 , d[1][i][u]);
} if(h2&(1<<i)){
if(d[0][i][v]>m1) m2=m1,m1=d[0][i][v];
else if(d[0][i][v]>m2) m2=d[0][i][v];
else m2=max(m2 , d[1][i][v]);
}
} if(m1==c) return c-m2;
else return c-m1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i){
int u,v; ll w;
scanf("%d%d%lld",&u,&v,&w);
e[i].from=u;
e[i].to=v;
e[i].val=w;
} kruskal();
for(int i=0;i<m;++i) if(used[i]){
a[e[i].from].push_back(i);
a[e[i].to].push_back(i);
} dep[1]=1; dfs(1);
for(int i=0;i<m;++i) if(!used[i]){
if(e[i].val-mx>ans) break;
ll t=get(e[i].from , e[i].to , e[i].val);
ans=min(ans , t);
} return printf("%lld
",res+ans),0;