题意
思考
严格次小生成树，就是求出严格的次小生成树~
次小生成树其实是很好求的，枚举每一个没选的边 ((u, v, d))，用它来替换 (u, v) 间的最大边即可，但是存在没选的边与要替换的边权值相等，那么就会出现次小生成树的权值等于最小生成树的权值，这样就不“严格”了。
当然求严格次小生成树也不是很难，只要利用倍增数组（边权塞进点里）记录点对间边权的最大值与严格次大值即可~细节看代码
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x * f;
}
const ll oo = 0x3f3f3f3f3f3f3f3f;
const ll M = 300030;
const ll N = 100010;
struct node{
ll nxt, from, to, dis;
}edge[M << 1], E[M];
ll head[N], num = 0;
void build(ll from, ll to, ll dis){
edge[++num].nxt = head[from];
edge[num].to = to;
edge[num].from = from;
edge[num].dis = dis;
head[from] = num;
}
bool cmp(node a, node b){ return a.dis < b.dis; }
ll d[N], f[N][20], MAX1[N][20], MAX2[N][20];
void dfs(ll u, ll fa){
for(ll i=head[u]; i; i=edge[i].nxt){
ll v = edge[i].to;
if(v == fa) continue;
f[v][0] = u; d[v] = d[u] + 1; MAX1[v][0] = edge[i].dis; MAX2[v][0] = -oo;
dfs(v, u);
}
}
ll lca(ll u, ll v){
if(d[u] < d[v]) swap(u, v);
for(ll i=18; i>=0; i--) if(d[f[u][i]] >= d[v]) u = f[u][i];
if(u == v) return u;
for(ll i=18; i>=0; i--) if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
}
ll fa[N], vis[M], n, m, sum;
ll findx(ll x){
if(fa[x] == x) return x;
return fa[x] = findx(fa[x]);
}
ll kruskal(){
ll sum = 0;
sort(E+1, E+m+1, cmp); ll js = 0;
for(ll i=1; i<=n; i++) fa[i] = i;
for(ll i=1; i<=m; i++){
ll u = E[i].from, v = E[i].to;
u = findx(u), v = findx(v);
if(u == v) continue;
fa[u] = v; build(E[i].from, E[i].to, E[i].dis); build(E[i].to, E[i].from, E[i].dis);
vis[i] = 1; js ++;
sum += E[i].dis;
if(js == n-1) return sum;
}
return -1;
}
ll query(ll u, ll v, ll now){
if(d[u] < d[v]) swap(u, v); ll ans = -oo;
for(ll i=18; i>=0; i--){
if(d[f[u][i]] >= d[v]){
if(now == MAX1[u][i]){
ans = max(ans, MAX2[u][i]);
}
else ans = max(ans, MAX1[u][i]);
u = f[u][i];
}
}
return ans;
}
int main(){
n = read(), m = read();
for(ll i=1; i<=m; i++){
E[i].from = read(), E[i].to = read(), E[i].dis = read();
}
sum = kruskal();
d[1] = 1; MAX2[1][0] = -oo;
dfs(1, 0);
for(ll j=1; j<=18; j++)
for(ll i=1; i<=n; i++){
f[i][j] = f[f[i][j-1]][j-1];
MAX1[i][j] = max(MAX1[i][j-1], MAX1[f[i][j-1]][j-1]);
MAX2[i][j] = max(MAX2[i][j-1], MAX2[f[i][j-1]][j-1]);
if(MAX1[i][j-1] > MAX1[f[i][j-1]][j-1]){
MAX2[i][j] = max(MAX2[i][j], MAX1[f[i][j-1]][j-1]);
}
else if(MAX1[i][j-1] < MAX1[f[i][j-1]][j-1]){
MAX2[i][j] = max(MAX1[i][j-1], MAX2[i][j]);
}
}
ll ans = 0x3f3f3f3f3f3f3f3f;
for(ll i=1; i<=m; i++){
if(!vis[i]){
ll u = E[i].from, v = E[i].to, d = E[i].dis;
ll LCA = lca(u, v);
ll Q = query(u, LCA, d);
ll Q2 = query(v, LCA, d);<< endl;
Q = max(Q, Q2);
ans = min(ans, sum - Q + E[i].dis);
}
}
cout << ans;
return 0;
}
总结
主要注意一下怎样记录严格次大值，怎样转移倍增数组（细节见代码，分类讨论要注意一下，我之前转移错了 (QWQ) ）