前言
这可以说是本蒟蒻打过最长的代码了
思路
先求出此图中的最小生成树 权值为tot 我们称这棵树中的n-1条边为“树边” 其他m-n+1条边为“非树边”
枚举每条非树边(x,y,z)添加到最小生成树中 可以在x,y之间构成一个环
设x,y之间的路径最大值为val1 次大值为val2（val1>val2）
则有以下两种情况
- 当z>val1时 则把val1对应的边换成(x,y,z) 得到一个候选值 权值和为tot-val1+z
- 当z=val1时 则把val2对应的边换成(x,y,z) 得到一个候选值 权值和为tot-val2+z
在所有候选值中取最小值 即可得出严格次小生成树
求出一条路径上的最大值和次大值可用树上倍增来预处理 设f[x][k]表示x的2辈祖先
m1[x][k]和m2[x][k]分别为路径上的最大值和次大值
可以得出：
f[x][k]=f[f[x][k-]][k-];
m1[x][k]=max(m1[x][k-],m1[f[x][k-]][k-]);//最大值等于两者中的最大值
if(m1[x][k-]==m1[f[x][k-]][k-])//如果两者中最大值相等
m2[x][k]=max(m2[x][k-],m2[f[x][k-]][k-]);//则取两边次大值中较大的作为次大值
if(m1[x][k-]<m1[f[x][k-]][k-])//如果前面最大小于后面最大
m2[x][k]=max(m1[x][k-],m2[f[x][k-]][k-]);//则取前面最大值与后面次大值中的较大值作为次大值
if(m1[x][k-]>m1[f[x][k-]][k-])//如果前面最大大于后面最大
m2[x][k]=max(m2[x][k-],m1[f[x][k-]][k-]);//则取前面次大值与后面最大值中的较大值作为次大值
当k=0时 各个初始化
f[x][0]=father(x)
m1[x][0]=edge(x,father(x))
m2[x][0]= -INF（不存在次大值）
最后 我们考虑每条非树边 用倍增计算其LCA(x,y)
当x,y每向上移动一段距离 就把该段路径的最大值和次大值合并到答案中
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define maxn 400001
#define ll long long
#define INF 2147483647000000//记得开大 数据很坑
ll n,m,cnt,k,tot,ans=INF;
ll fa[maxn],h[maxn],dep[maxn],f[maxn][],m1[maxn][],m2[maxn][];
bool vis[maxn];
struct Edge
{
ll w;
ll nex;
ll to;
}e[maxn];//最小生成树的变
struct Node
{
ll l,r,w;
}node[maxn];//节点
void add(ll u,ll v,ll w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nex=h[u];
h[u]=cnt;
}
bool cmp(Node a,Node b)
{
return a.w<b.w;
}
ll find(ll x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void unionn(ll x,ll y)
{
ll f1=find(x);
ll f2=find(y);
if(f1!=f2)
fa[f1]=f2;
}
void kruskal()//最小生成树
{
sort(node+,node++m,cmp);
for(ll i=;i<=m;i++)
{
if(find(node[i].l)!=find(node[i].r))
{
unionn(node[i].l,node[i].r);
vis[i]=;//判断此边是最小生成树中的边
tot+=node[i].w;//计算最小生成树权值
add(node[i].l,node[i].r,node[i].w);
add(node[i].r,node[i].l,node[i].w);
k++;
}
if(k==n-) break;
}
}
void deal(ll u,ll father)//预处理
{
f[u][]=father;
for(ll i=h[u];i;i=e[i].nex)
{
ll v=e[i].to;
if(v==father) continue;
dep[v]=dep[u]+;//不是父亲时
m1[v][]=e[i].w;//最大值等于此边权值
m2[v][]=-INF;//此大值为极小值 因为此时只有一个值
deal(v,u);
}
}
void pre()//计算出所有的值
{
for(ll x=;x<=;x++)//注意先循环步数
{
for(ll k=;k<=n;k++)
{
f[x][k]=f[f[x][k-]][k-];
m1[x][k]=max(m1[x][k-],m1[f[x][k-]][k-]);//最大值等于两者中的最大值
if(m1[x][k-]==m1[f[x][k-]][k-])//如果两者中最大值相等
m2[x][k]=max(m2[x][k-],m2[f[x][k-]][k-]);//则取两边次大值中较大的作为次大值
if(m1[x][k-]<m1[f[x][k-]][k-])//如果前面最大小于后面最大
m2[x][k]=max(m1[x][k-],m2[f[x][k-]][k-]);//则取前面最大值与后面次大值中的较大值作为次大值
if(m1[x][k-]>m1[f[x][k-]][k-])//如果前面最大大于后面最大
m2[x][k]=max(m2[x][k-],m1[f[x][k-]][k-]);//则取前面次大值与后面最大值中的较大值作为次大值
}
}
}
ll lca(ll x,ll y)//倍增求LCA
{
if(dep[x]<dep[y]) swap(x,y);
for(ll k=;k>=;k--)
{
if(dep[f[x][k]]>=dep[y]) x=f[x][k];
if(x==y) return x;
}
for(ll i=;i>=;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][];
}
ll findmax(ll x,ll t,ll val)//找出最大值
{
ll temp=-INF;
for(ll i=;i>=;i--)
{
if(dep[f[x][i]]>=dep[t])//比LCA深的话
{
if(m1[x][i]==val) temp=max(temp,m2[x][i]);//如果当前最大值等于此路径上最大值 则取次大值替换此边
else temp=max(temp,m1[x][i]);//如果大于最大值 则取最大值替换此边
x=f[x][i];
}
}
return temp;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=;i<=n;i++) fa[i]=i;
for(ll i=;i<=m;i++) scanf("%lld%lld%lld",&node[i].l,&node[i].r,&node[i].w);
kruskal();
m2[][]=-INF;//初始化
dep[]=;
deal(,);
pre();
for(ll i=;i<=m;i++)//枚举每条非最小生成树边
{
if(vis[i]) continue;//当此边为最小生成树中的边时 跳过
ll x=node[i].l;
ll y=node[i].r;
ll z=node[i].w;
ll t=lca(x,y);
ll v1=findmax(x,t,z);//找出候选最大值 从x到lca(x,y)的路径最大
ll v2=findmax(y,t,z);//从y到lca(x,y)的路径最大
ans=min(ans,tot+z-max(v1,v2));//比较出一个最小值
}
printf("%lld",ans);
}