题目描述
给定一张 N 个点 M 条边的无向图，求无向图的严格次小生成树。
设最小生成树的边权之和为sum，严格次小生成树就是指边权之和大于sum的生成树中最小的一个。
输入格式
第一行包含两个整数N和M。
接下来M行，每行包含三个整数x，y，z，表示点x和点y之前存在一条边，边的权值为z。
输出格式
包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)
数据范围
N≤105,M≤3∗105
样例
输入样例：
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
输出样例：
11
严格次小生成树
这是对1148题：秘密的牛奶运输，求严格次小生成树的优化
https://www.acwing.com/solution/content/14583/
同样是先建立最小生成树，再枚举非树边，枚举非树边加入最小生成树一定会形成环，删除环中边权最大的边（如果最大的边和加入的边相等，那么删去次大边）。而枚举非树边的时候，所形成的环中，层数最小的点一定是他们的最近公共祖先（树从上往下层数增加）。
而在用倍增算法求最近公共祖先的时候（倍增算法求最近公共祖先见1172题：祖孙询问 https://www.acwing.com/solution/content/14916/ ） ，一层一层往上跳的时候，整个环上除了新加入的非树边外，其他边的权值的最大值和次大值可以同时处理出来。而这里在处理的时候由于跳的时候每次跳2^j步，所以就是在这里对原来求严格次小生成树进行了优化，从n^2变为了nlogn。
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=3*N,INF=0x3f3f3f3f;
typedef long long LL;
struct Edge{
int a,b,w;
bool used;
bool operator<(const Edge& t)const{
return w<t.w;
}
}e[M];
int n,m;
int p[N];
int q[N];
int depth[N],fa[N][17],d1[N][17],d2[N][17];
int h[N],ed[2*N],ne[2*N],we[2*N],idx;
void add(int a,int b,int c){
ed[idx]=b,we[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int find(int x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
LL kruskal(){
for(int i=1;i<=n;i++) p[i]=i;
sort(e,e+m);
LL res=0;
for(int i=0;i<m;i++){
int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
if(a!=b){
p[a]=b;
res+=w;
e[i].used=1;//记录是树边
}
}
return res;
}
void build(){
memset(h,-1,sizeof h);
for(int i=0;i<m;i++){
if(e[i].used){
int a=e[i].a,b=e[i].b,c=e[i].w;
add(a,b,c),add(b,a,c);
}
}
}
void bfs(){
//预处理层数，同时处理每两个点之间的最大值和次大值
memset(depth,0x3f,sizeof depth);
depth[0]=0,depth[1]=1;
int hh=0,tt=-1;
q[++tt]=1;
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];~i;i=ne[i]){
int j=ed[i];
if(depth[j]>depth[t]+1){
depth[j]=depth[t]+1;
q[++tt]=j;
fa[j][0]=t;
//处理每跳2^j步的路径上的最大值和次大值
//在求lca的时候，a,b两个点向上跳一直到最近公共祖先时，就可以依靠这个来求得整条a到b的最大值和次大值
d1[j][0]=we[i],d2[j][0]=-INF;//开始只有一条边，所以没有严格次大值
for(int k=1;k<=16;k++){
int anc=fa[j][k-1];//先跳2^(k-1)到达的中间节点
fa[j][k]=fa[anc][k-1];
//跳2^k步，那么分两步走，先跳2^(k-1)到anc,再跳2^(k-1),那么这2^k路径中
//最大值和严格次大值一定在这两次跳跃的最大和严格次大中产生
int dis[4]={d1[j][k-1],d2[j][k-1],d1[anc][k-1],d2[anc][k-1]};
d1[j][k]=-INF,d2[j][k]=-INF;
for(int u=0;u<4;u++){
int d=dis[u];
if(d>d1[j][k]){
d2[j][k]=d1[j][k];
d1[j][k]=d;
}
else if(d!=d1[j][k]&&d>d2[j][k])
d2[j][k]=d;
}
}
}
}
}
}
LL lca(int a,int b,int w){
int dis[N*2];
if(depth[a]<depth[b]) swap(a,b);
int cnt=0;//在不断上调的过程中，会有许多最大值和次大值，依次记录
for(int i=16;i>=0;i--){
if(depth[fa[a][i]]>=depth[b]){
dis[cnt++]=d1[a][i];
dis[cnt++]=d2[a][i];
a=fa[a][i];
}
}
//跳到同一层后，一起上跳
if(a!=b){
for(int i=16;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
dis[cnt++]=d1[a][i];
dis[cnt++]=d2[a][i];
dis[cnt++]=d1[b][i];
dis[cnt++]=d2[b][i];
a=fa[a][i];
b=fa[b][i];
}
}
//跳到最近公共祖先的下一层后，再上调一层，且跳一步是没有次大值的
dis[cnt++]=d1[a][0];
dis[cnt++]=d1[b][0];
}
int dist1=-INF,dist2=-INF;//计算在a到b路径中整体的最大值和次大值
for(int i=0;i<cnt;i++){
int d=dis[i];
if(d>dist1){
dist2=dist1;
dist1=d;
}
else if(d!=dist1&&d>dist2) dist2=d;
}
if(w>dist1) return w-dist1;//如果a到b的路径上dist1小于新加入的非树边，那么将删除dist1
if(w>dist2) return w-dist2;//如果a到b的路径上dist1不小于新加入的非树边，那么考虑次大
return INF;//否则说明没有严格次大生成树
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
e[i]={a,b,c};
}
LL sum=kruskal();
build();//将最小生成树建立起来
bfs();//做lca之前的初始化
LL ans=1e18;
for(int i=0;i<m;i++){
if(!e[i].used){
int a=e[i].a,b=e[i].b,w=e[i].w;
ans=min(ans,sum+lca(a,b,w));
}
}
cout<<ans<<endl;
return 0;
}
