链接
https://www.luogu.com.cn/problem/P4180
题意
求严格次小生成树
思路
先求出最小生成树
记不在最小生成树里的边为非树边，在最小生成树上添加一条非树边会使这条边的两端 $x,y$ 形成一个环
若这条非树边大于 $x$ 到 $y$ 的路径上的最大边，那么可以替换它，现在的这颗树就是候选次小生成树
若这条非树边等于 $x$ 到 $y$ 的路径上的最大边，那么可以替换路径上的次大边，现在的这颗树就是候选次小生成树
因此我们只需要求出每条路径上的最大边和次大边即可
我们可以利用向上倍增求 LCA 的思想，求出 $x$ 到其 $2^k$ 辈祖先之间的最大边和次大边，记 $g[x,k,0]$ 为 $x$ 到其 $2^k$ 辈祖先之间的最大边，$g[x,k,1]$ 为次大边：
$g[x,k,0]=max(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}$
最后扫一遍所有的非树边，求出非树边所在环上的最大边和次大边，更新答案即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #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;
}
|