洛谷P4180：https://www.luogu.org/problemnew/show/P4180
前言
这可以说是本蒟蒻打过最长的代码了
思路
先求出此图中的最小生成树 权值为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的2k辈祖先
m1[x][k]和m2[x][k]分别为路径上的最大值和次大值
可以得出：
f[x][k]=f[f[x][k-1]][k-1]; m1[x][k]=max(m1[x][k-1],m1[f[x][k-1]][k-1]);//最大值等于两者中的最大值 if(m1[x][k-1]==m1[f[x][k-1]][k-1])//如果两者中最大值相等 m2[x][k]=max(m2[x][k-1],m2[f[x][k-1]][k-1]);//则取两边次大值中较大的作为次大值 if(m1[x][k-1]<m1[f[x][k-1]][k-1])//如果前面最大小于后面最大 m2[x][k]=max(m1[x][k-1],m2[f[x][k-1]][k-1]);//则取前面最大值与后面次大值中的较大值作为次大值 if(m1[x][k-1]>m1[f[x][k-1]][k-1])//如果前面最大大于后面最大 m2[x][k]=max(m2[x][k-1],m1[f[x][k-1]][k-1]);//则取前面次大值与后面最大值中的较大值作为次大值
当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][32],m1[maxn][32],m2[maxn][32]; 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+1,node+1+m,cmp); for(ll i=1;i<=m;i++) { if(find(node[i].l)!=find(node[i].r)) { unionn(node[i].l,node[i].r); vis[i]=1;//判断此边是最小生成树中的边 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-1) break; } } void deal(ll u,ll father)//预处理 { f[u][0]=father; for(ll i=h[u];i;i=e[i].nex) { ll v=e[i].to; if(v==father) continue; dep[v]=dep[u]+1;//不是父亲时 m1[v][0]=e[i].w;//最大值等于此边权值 m2[v][0]=-INF;//此大值为极小值 因为此时只有一个值 deal(v,u); } } void pre()//计算出所有的值 { for(ll x=1;x<=18;x++)//注意先循环步数 { for(ll k=1;k<=n;k++) { f[x][k]=f[f[x][k-1]][k-1]; m1[x][k]=max(m1[x][k-1],m1[f[x][k-1]][k-1]);//最大值等于两者中的最大值 if(m1[x][k-1]==m1[f[x][k-1]][k-1])//如果两者中最大值相等 m2[x][k]=max(m2[x][k-1],m2[f[x][k-1]][k-1]);//则取两边次大值中较大的作为次大值 if(m1[x][k-1]<m1[f[x][k-1]][k-1])//如果前面最大小于后面最大 m2[x][k]=max(m1[x][k-1],m2[f[x][k-1]][k-1]);//则取前面最大值与后面次大值中的较大值作为次大值 if(m1[x][k-1]>m1[f[x][k-1]][k-1])//如果前面最大大于后面最大 m2[x][k]=max(m2[x][k-1],m1[f[x][k-1]][k-1]);//则取前面次大值与后面最大值中的较大值作为次大值 } } } ll lca(ll x,ll y)//倍增求LCA { if(dep[x]<dep[y]) swap(x,y); for(ll k=18;k>=0;k--) { if(dep[f[x][k]]>=dep[y]) x=f[x][k]; if(x==y) return x; } for(ll i=18;i>=0;i--) { if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } } return f[x][0]; } ll findmax(ll x,ll t,ll val)//找出最大值 { ll temp=-INF; for(ll i=18;i>=0;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=1;i<=n;i++) fa[i]=i; for(ll i=1;i<=m;i++) scanf("%lld%lld%lld",&node[i].l,&node[i].r,&node[i].w); kruskal(); m2[1][0]=-INF;//初始化 dep[1]=1; deal(1,0); pre(); for(ll i=1;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); }