連結
https://www.luogu.com.cn/problem/P4180
題意
求嚴格次小生成樹
思路
先求出最小生成樹
記不在最小生成樹裡的邊為非樹邊，在最小生成樹上添加一條非樹邊會使這條邊的兩端 x , y x,y x,y 形成一個環
若這條非樹邊大于 x x x 到 y y y 的路徑上的最大邊，那麼可以替換它，現在的這顆樹就是候選次小生成樹
若這條非樹邊等于 x x x 到 y y y 的路徑上的最大邊，那麼可以替換路徑上的次大邊，現在的這顆樹就是候選次小生成樹
是以我們隻需要求出每條路徑上的最大邊和次大邊即可
我們可以利用向上倍增求 LCA 的思想，求出 x x x 到其 2 k 2^k 2k 輩祖先之間的最大邊和次大邊，記 g [ x , k , 0 ] g[x,k,0] g[x,k,0] 為 x x x 到其 2 k 2^k 2k 輩祖先之間的最大邊， g [ x , k , 1 ] g[x,k,1] g[x,k,1] 為次大邊：
g [ x , k , 0 ] = m a x ( g [ x , k − 1 , 0 ] , g [ f [ x , k − 1 ] , k − 1 , 0 ] ) g[x,k,0]=max(g[x,k-1,0],g[f[x,k-1],k-1,0]) g[x,k,0]=max(g[x,k−1,0],g[f[x,k−1],k−1,0])
g [ x , k , 1 ] = { m a x ( g [ x , k − 1 , 1 ] , g [ f [ x , k − 1 ] , k − 1 , 1 ] ) g [ x , k − 1 , 0 ] = g [ f [ x , k − 1 ] , k − 1 , 0 ] m a x ( g [ x , k − 1 , 1 ] , g [ f [ x , k − 1 ] , k − 1 , 0 ] ) g [ x , k − 1 , 0 ] > g [ f [ x , k − 1 ] , k − 1 , 0 ] m a x ( g [ x , k − 1 , 0 ] , g [ f [ x , k − 1 ] , k − 1 , 1 ] ) g [ x , k − 1 , 0 ] < g [ f [ x , k − 1 ] , k − 1 , 0 ] g[x,k,1]=\begin{cases} max(g[x,k-1,1],g[f[x,k-1],k-1,1]) & g[x,k-1,0]=g[f[x,k-1],k-1,0]\\ max(g[x,k-1,1],g[f[x,k-1],k-1,0]) & g[x,k-1,0]>g[f[x,k-1],k-1,0]\\ max(g[x,k-1,0],g[f[x,k-1],k-1,1]) & g[x,k-1,0]<g[f[x,k-1],k-1,0] \end{cases} g[x,k,1]=⎩⎪⎨⎪⎧max(g[x,k−1,1],g[f[x,k−1],k−1,1])max(g[x,k−1,1],g[f[x,k−1],k−1,0])max(g[x,k−1,0],g[f[x,k−1],k−1,1])g[x,k−1,0]=g[f[x,k−1],k−1,0]g[x,k−1,0]>g[f[x,k−1],k−1,0]g[x,k−1,0]<g[f[x,k−1],k−1,0]
最後掃一遍所有的非樹邊，求出非樹邊所在環上的最大邊和次大邊，更新答案即可
代碼
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
const int M=300010;
int n,m;
int cnt,to[M],val[M],nxt[M],head[N];
int fa[N],t,d[N],f[N][25],g[N][25][2];
bool st[M];
ll mx;
struct edge {
int u,v,w;
bool operator < (const edge &a) const {
return w<a.w;
}
}e[M];
void addedge(int u,int v,int w) {
cnt++;
to[cnt]=v;
val[cnt]=w;
nxt[cnt]=head[u];
head[u]=cnt;
}
int get(int x) {
if(x==fa[x]) return x;
return fa[x]=get(fa[x]);
}
void kruskal() {
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+m);
for(int i=1;i<=m;i++) {
int a=get(e[i].u),b=get(e[i].v);
if(a==b) continue;
fa[a]=b;
mx+=e[i].w*1ll;
st[i]=true;
addedge(e[i].u,e[i].v,e[i].w);
addedge(e[i].v,e[i].u,e[i].w);
}
}
void bfs() {
queue<int>q;
q.push(1);
d[1]=1;
while(q.size()) {
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
if(v==f[u][0]) continue;
d[v]=d[u]+1;
f[v][0]=u;
for(int j=1;j<=t;j++) f[v][j]=f[f[v][j-1]][j-1];
g[v][0][0]=val[i];
g[v][0][1]=0;
for(int j=1;j<=t;j++) {
g[v][j][0]=max(g[v][j-1][0],g[f[v][j-1]][j-1][0]);
if(g[v][j-1][0]==g[f[v][j-1]][j-1][0]) g[v][j][1]=max(g[v][j-1][1],g[f[v][j-1]][j-1][1]);
else if(g[v][j-1][0]<g[f[v][j-1]][j-1][0]) g[v][j][1]=max(g[v][j-1][0],g[f[v][j-1]][j-1][1]);
else if(g[v][j-1][0]>g[f[v][j-1]][j-1][0]) g[v][j][1]=max(g[v][j-1][1],g[f[v][j-1]][j-1][0]);
}
q.push(v);
}
}
}
int LCA(int a,int b) {
if(d[a]>d[b]) swap(a,b);
for(int i=t;i>=0;i--) if(d[f[b][i]]>=d[a]) b=f[b][i];
if(a==b) return b;
for(int i=t;i>=0;i--) if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
return f[a][0];
}
pair<int,int> cal(int u,int v) {
pair<int,int>res(0,0);
int lca=LCA(u,v);
for(int i=t;i>=0;i--) {
if(d[f[u][i]]>=d[lca]) {
if(g[u][i][0]>res.first) {
res.second=max(res.second,max(res.first,g[u][i][1]));
res.first=g[u][i][0];
}
else res.second=max(res.second,g[u][i][0]);
u=f[u][i];
}
}
for(int i=t;i>=0;i--) {
if(d[f[v][i]]>=d[lca]) {
if(g[v][i][0]>res.first) {
res.second=max(res.second,max(res.first,g[v][i][1]));
res.first=g[v][i][0];
}
else res.second=max(res.second,g[v][i][0]);
v=f[v][i];
}
}
return res;
}
void solve() {
long long ans=0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=m;i++) {
if(st[i]) continue;
pair<int,int> res=cal(e[i].u,e[i].v);
if(e[i].w>res.first) ans=min(ans,mx-res.first+e[i].w);
else if(e[i].w==res.first&&e[i].w>res.second) ans=min(ans,mx-res.second+e[i].w);
}
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
t=(int)log(n)/log(2)+1;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
kruskal();
bfs();
solve();
return 0;
}