[洛谷] [最小生成树] [并查集判环] P4180 严格次小生成树
题意
求无向图
思路
-
引理：严格次小生成树与最小生成树只有一条边的差异
证明十分简单，因为换更多边一定不优。
-
倍增 + LCA + 最小生成树
首先是换边操作：加入一条边，再删去一条边。
那不妨先建出最小生成树，令其权值和为
val 。然后枚举如何加边。设新加入
e(u,v) ，权值为w ，而加入后删去的边的权值为ws 。删边也不能乱删。显然，最小生成树加入一条边后必定会产生一个环，因此需删去环中（原生成树中）的一边。
为了使得新生成树尽可能小，删去的这一边需要尽可能大。
由于题目要求的是严格次小生成树，所以要找环上与
w 不同且最大的边，这意味着要求环上最大边和严格次大边。由于是在树上操作，所以环中的边就是
u 到LCA(u,v) 和v 到LCA(u,v) 的路径上的边。于是问题变为：快速找出树上两点的简单路径上的最大边和严格次大边。
考虑倍增解决，定义：
运用倍增数组，我们便可求出环中的最大边和次大边，也就能得到
ws 。最后，加入
e(u,v) 后的次小生成树的权值和便为：val-ws+w 。求
\max\limits_{i≤m} {val-ws_i+w_i} 即可。 -
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=3e5+5;
const long long INF=1000000000000005;
int n,m,u[M],v[M],cnt,fa[N],tot,head[N],id[M];
long long w[M],ans,sum,lg[N],jump[N][25],dep[N],Max[N][25],Max2[N][25],z,d[6];
struct edge{
int u,v,jl;
long long w;
}a[2*M];
struct qxx{
int v,nxt;
long long w;
}e[2*M];
inline void insert(int u,int v,long long w,int jl){
a[++cnt].u=u;
a[cnt].v=v;
a[cnt].w=w;
a[cnt].jl=jl;
}
inline bool cmp(edge x,edge y){
return x.w<y.w;
}
inline int find(int k){
if(fa[k]==k){
return k;
}
return fa[k]=find(fa[k]);
}
inline void add(int u,int v,long long w){
e[++tot].v=v;
e[tot].nxt=head[u];
e[tot].w=w;
head[u]=tot;
}
inline void kruskal(){
sort(a+1,a+1+cnt,cmp);
for(int i=1; i<=cnt;i++){
int fu,fv;
long long w;
fu=find(a[i].u);
fv=find(a[i].v);
w=a[i].w;
if(fu^fv){
fa[fu]=fv;
id[a[i].jl]=1;
add(a[i].u,a[i].v,w);
add(a[i].v,a[i].u,w); //用 kruskal 方便建边
sum+=w;
}
}
}
inline void dfs(int u,int fa){
dep[u]=dep[fa]+1;
for(int i=1; i<=lg[dep[u]];++i){ //倍增的预处理
jump[u][i]=jump[jump[u][i-1]][i-1];
if(Max[u][i-1]^Max[jump[u][i-1]][i-1]){
Max[u][i]=max(Max[u][i-1],Max[jump[u][i-1]][i-1]);
Max2[u][i]=min(Max[u][i-1],Max[jump[u][i-1]][i-1]);
}
else{
Max[u][i]=Max[u][i-1];
Max2[u][i]=max(Max2[u][i-1],Max2[jump[u][i-1]][i-1]);
}
}
for(int i=head[u]; i;i=e[i].nxt){
int v=e[i].v;
if(v^fa){
Max[v][0]=e[i].w;
jump[v][0]=u;
dfs(v,u);
}
}
}
inline int LCA(int x,int y){
if(dep[x]<dep[y]){
swap(x,y);
}
for(int i=lg[dep[x]]; i>=0;i--){
if(dep[jump[x][i]]>=dep[y]){
x=jump[x][i];
}
}
if(x==y){
return x;
}
for(int i=lg[dep[x]]; i>=0;i--){
if(jump[x][i]^jump[y][i]){
x=jump[x][i];
y=jump[y][i];
}
}
return jump[x][0];
}
inline int getmax(int x,int y){ //路径上的最大边
long long ma=-1; //不存在就为 -1
for(int i=lg[dep[x]]; i>=0;i--){
if(dep[jump[x][i]]>=dep[y]){
ma=max(ma,Max[x][i]);
x=jump[x][i];
}
}
return ma;
}
inline int getmax2(int x,int y){
long long m1=-1,m2=-1; //不存在就为 -1
for(int i=lg[dep[x]]; i>=0;i--){
if(dep[jump[x][i]]>=dep[y]){
if(Max[x][i]>m1){
m2=m1;
m1=Max[x][i];
}
else{
if(Max[x][i]>m2){
m2=Max[x][i];
}
}
if(Max2[x][i]>m1){
m2=m1;
m1=Max2[x][i];
}
else{
if(Max2[x][i]>m2){
m2=Max2[x][i];
}
}
x=jump[x][i];
}
}
return m2;
}
int main(){
cin>>n>>m;
for(int i=1; i<=n;i++){
fa[i]=i;
}
for(int i=1; i<=m;++i){
scanf("%d%d%lld",&u[i],&v[i],&w[i]);
if(u[i]==v[i]){
continue; //忽略重边
}
insert(u[i],v[i],w[i],i);
insert(v[i],u[i],w[i],i);
}
kruskal();
memset(Max,-1,sizeof Max);
memset(Max2,-1,sizeof Max2); //如果不存在则为 -1
for(int i=2; i<=n;i++){
lg[i]=lg[i>>1]+1;
}
dfs(1,0);
ans=INF;
for(int i=1; i<=m;i++){
if(!id[i]){
int x,y,k;
x=u[i];
y=v[i];
k=LCA(x,y);
d[1]=getmax(x,k);
d[2]=getmax2(x,k);
d[3]=getmax(y,k);
d[4]=getmax2(y,k);
sort(d+1,d+5);
int qq=4;
while(qq&&d[qq]==w[i]){ //注意不能相同，相同就向下继续找
qq--;
}
z=d[qq];
if(z^-1){
ans=min(ans,sum-z+w[i]);
}
}
}
cout<<ans;
return 0;
}