1555：【例 4】次小生成树
这次是在图里面求严格次小生成树
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1e5+10;
const int M=3e5+10;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
/*
https://blog.csdn.net/regina8023/article/details/44814899
https://blog.csdn.net/YYHS_WSF/article/details/82842355
求出最小生成树，枚举每一条非树边，用它取代掉环上最大的边最优。
那么相当于求两点到lca的最大边权，直接倍增做。
但是要注意是严格最小生成树，那么这条非树边与环上最大边相同时可能取代掉的是环上的次大边，那么倍增的时候多维护一个严格次大的边即可。
*/
int n,m;
struct node{
int u,v,wei;
}ed[M];
queue<int> q;
struct edge{
int to,next,w;
}e[M*2];
struct ma{
int a,b; //分别是 最大、次大
}g[maxn][21],p;
int head[maxn],dep[maxn],f[maxn][21],fa[maxn]; //后两个：深度，倍增数组
int vis[M];
bool cmp(node a,node b){
return a.wei<b.wei;
}
int findd(int x){
if(x==fa[x]) return x;
else return fa[x]=findd(fa[x]);
}
LL mst=0;
void kru(){
sort(ed+1,ed+1+m,cmp);
int cnt=1;
for(int i=1;i<=m;i++){
int fa1=findd(ed[i].u);
int fa2=findd(ed[i].v);
if(fa1!=fa2){
cnt++;
vis[i]=1;
mst+=ed[i].wei;
fa[fa1]=fa2;
}
}
}
int tot;
void adde(int x,int y,int z){
e[++tot].to=y;
e[tot].next=head[x];
e[tot].w=z;
head[x]=tot;
e[++tot].to=x;
e[tot].next=head[y];
e[tot].w=z;
head[y]=tot;
}
void build(){
for(int i=1;i<=m;i++){
if(vis[i]) adde(ed[i].u,ed[i].v,ed[i].wei); //建立树边
}
g[1][0].a=g[1][1].b=-INF; //最小值
f[1][0]=0; //根的爸爸
dep[1]=1;
q.push(1);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y==f[x][0]) continue; //是爸爸
f[y][0]=x;
dep[y]=dep[x]+1;
g[y][0].a=e[i].w; //最大值的初值
q.push(y);
}
}
}
void updat(ma &x,ma y){ ///用y来更新x
if(x.a>y.a) x.b=max(y.a,x.b); //b记录的是次大 ，这三行都是在更新次大
else if(x.a<y.a) x.b=max(x.a,y.b);
else x.b=max(x.b,y.b);
x.a=max(x.a,y.a); //最大直接更新
}
void ST(){
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
updat(g[i][j],g[i][j-1]);
updat(g[i][j],g[f[i][j-1]][j-1]);
}
}
}
void mov(int &x,int deep){ //先移动到同一层
for(int i=20;i>=0;i--){
if(dep[f[x][i]]>=deep) {
updat(p,g[x][i]);
x=f[x][i];
}
}
}
void getlca(int x,int y){
p.a=p.b=-INF;
if(dep[x]>dep[y]) swap(x,y);
mov(y,dep[x]); //先移动到同一层
if(x==y) return;
for(int i=20;i>=0;i--){
if(f[x][i]!=f[y][i]){
updat(p,g[x][i]);
updat(p,g[y][i]); //找到替换的那条边严格最大边
x=f[x][i];
y=f[y][i];
}
}
updat(p,g[x][0]);
updat(p,g[y][0]);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&ed[i].u,&ed[i].v,&ed[i].wei);
}
for(int i=1;i<=n;i++) fa[i]=i;
kru(); //先求出最小生成树的权值
build(); //用非树边去更新倍增数组，g[][].a g[][].b
ST();
LL ans=(LL)1e15; //这个要设置的足够大
for(int i=1;i<=m;i++){
if(!vis[i]){ //用非树边建立
getlca(ed[i].u,ed[i].v);
if(p.a==ed[i].wei){ //最大便与其相等
ans=min(ans,mst+ed[i].wei-p.b);
}
else ans=min(ans,mst+ed[i].wei-p.a);
}
}
printf("%lld
",ans);
return 0;
}