洛谷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);
}
转载于:https://www.cnblogs.com/BrokenString/p/9775474.html
相关资源：JAVA上百实例源码以及开源项目
