次小生成树
定义：边权之和大于最小生成树边权之和的生成树中最小的一个
思路：枚举所有未连接的边连上，那么一定会出现一个环，再去掉环上最大的边（如果与新加的边等大就要去次小边），这个最小值就为次小生成树的值
朴素求法：先用kruskal求出最小生成树，然后从每个点开始找到其他点的最大边与次大边，然后枚举所有边
复杂度\(O(n^2+m)\)
LAC优化：就是只讨论一棵树，对每个点记录向上跳\(2^i\)经过的最大边与次大边
注意LAC的i=0时的特殊处理
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
const int N = 1e5 + 10,M = 3e5 + 10;
int n,m,sum;
vector<PII> ed[N];//新图
struct edge{int u,v,len;
bool operator<(const edge &x)const{return len < x.len;}};
edge _ed[M];//旧图
int pre[N];//并查集
bool use[M];//边使用
void init(){for(int i = 1;i <= n;i++) pre[i] = i;}//并查集初始化
int find(int x){if(pre[x] == x) return pre[x];else return pre[x] = find(pre[x]);}
void kruskal(){
init();
sort(_ed + 1,_ed + 1 + m);
for(int i = 1;i <= m;i++){
if(find(_ed[i].u) != find(_ed[i].v)){
use[i] = 1;
sum += _ed[i].len;
pre[find(_ed[i].u)] = find(_ed[i].v);
ed[_ed[i].u].push_back({_ed[i].v,_ed[i].len});
ed[_ed[i].v].push_back({_ed[i].u,_ed[i].len});
}
}
}
int dep[N],fa[N][21] = {0};
PII ma[N][21];
void bfs(){
queue<int> qu;
qu.push(1);
dep[1] = 1;
while(!qu.empty()){
int u = qu.front();
qu.pop();
for(auto e:ed[u]){
int v = e.fi,len = e.se;
if(dep[v]) continue;
qu.push(v);
dep[v] = dep[u] + 1;
fa[v][0] = u;
ma[v][0].fi = len,ma[v][0].se = -1;
for(int i = 1;i <= 20;i++){
int faa = fa[v][i - 1];
fa[v][i] = fa[faa][i - 1];
ma[v][i].fi = max(ma[v][i-1].fi,ma[faa][i-1].fi);
if(ma[v][i-1].fi == ma[faa][i-1].fi) ma[v][i].se = max(ma[v][i-1].se,ma[faa][i-1].se);
else ma[v][i].se = min(ma[v][i-1].fi,ma[faa][i-1].fi);
}
}
}
}
int d[N];
int lca(int x,int y,int w){
int idx = 0;
if(dep[x] < dep[y]) swap(x,y);//让x深度更深
for(int i = 20;i >= 0;i--){//到同一深度
if(dep[fa[x][i]] >= dep[y]){
d[++idx] = ma[x][i].fi;
d[++idx] = ma[x][i].se;
x = fa[x][i];
}
}
if(x != y){
for(int i = 20;i >= 0;i--){
if(fa[x][i] != fa[y][i] || i == 0){
d[++idx] = ma[x][i].fi;
d[++idx] = ma[x][i].se;
d[++idx] = ma[y][i].fi;
d[++idx] = ma[y][i].se;
x = fa[x][i];
y = fa[y][i];
if(i == 0 && x != y)
i++;
}
}
}
int ma = -1;
for(int i = 1;i <= idx;i++)
if(d[i] != w && d[i] > ma) ma = d[i];
if(ma == -1)
return 1e18;
return - ma + w;
}
signed main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
int x,y,z;cin >> x >> y >> z;
_ed[i] = {x,y,z};
}
kruskal();
bfs();
int ans = 1e18;
for(int i = 1;i <= m;i++){
if(use[i]) continue;
ans = min(ans,sum + lca(_ed[i].u,_ed[i].v,_ed[i].len));
}
cout << ans << endl;
}