P4180 【模板】严格次小生成树[BJWC2010]
斯德哥尔摩
2018-07-30 18:01:44
[P4180 【模板】严格次小生成树[BJWC2010]](https://www.luogu.org/problemnew/show/P4180)
这题我刚拿到的时候，第一想法是先跑一遍$Kruskal$，然后依次加上未选的边，$LCT$维护动态最小生成树。
但是被自己造的数据$hack$了，尴尬。。。
然后一想，次小生成树一定是最小生成树删掉某条边，加上某条边，一定只涉及到两条边，不然就不是严格次小生成树。
那么我们可以求出加上的边与删除的边的差值的最小值，仍然用$LCT$维护。
但是这次不但要维护最大值，还要维护次大值。
然后就是板子了。
注：
1. $LCT$自带$32-34$倍常数，请注意优化。（吸氧我也不阻止）
2. 一开始$WA\ 30 * 2$，然后调了调发现手残把$pushup$敲炸了，尴尬。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 400010
#define MAX (1LL<<31)
using namespace std;
int n,m,fa[MAXN];
struct Graph{
int u,v,w;
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
namespace LCT{
int top=0,stack[MAXN];
struct Link_Cut_Tree{
int son[2];
int f,v,v_one,v_two,flag;
}a[MAXN];
inline bool isroot(int rt){
return a[a[rt].f].son[0]!=rt&&a[a[rt].f].son[1]!=rt;
}
inline void pushup(int rt){
if(!rt)return;
int lson=a[rt].son[0],rson=a[rt].son[1];
if(a[lson].v_one>a[rson].v_one){
a[rt].v_one=a[lson].v_one;
a[rt].v_two=max(a[lson].v_two,a[rson].v_one);
}
else if(a[rson].v_one>a[lson].v_one){
a[rt].v_one=a[rson].v_one;
a[rt].v_two=max(a[rson].v_two,a[lson].v_one);
}
else{
a[rt].v_one=a[lson].v_one;
a[rt].v_two=max(a[lson].v_two,a[rson].v_two);
}
if(a[rt].v>a[rt].v_one){
a[rt].v_two=a[rt].v_one;
a[rt].v_one=a[rt].v;
}
else if(a[rt].v!=a[rt].v_one&&a[rt].v>a[rt].v_two)a[rt].v_two=a[rt].v;
}
inline void pushdown(int rt){
if(!rt||!a[rt].flag)return;
a[a[rt].son[0]].flag^=1;a[a[rt].son[1]].flag^=1;a[rt].flag^=1;
swap(a[rt].son[0],a[rt].son[1]);
}
inline void turn(int rt){
int x=a[rt].f,y=a[x].f,k=a[x].son[0]==rt?1:0;
if(!isroot(x)){
if(a[y].son[0]==x)a[y].son[0]=rt;
else a[y].son[1]=rt;
}
a[rt].f=y;a[x].f=rt;a[a[rt].son[k]].f=x;
a[x].son[k^1]=a[rt].son[k];a[rt].son[k]=x;
pushup(x);pushup(rt);
}
void splay(int rt){
top=0;
stack[++top]=rt;
for(int i=rt;!isroot(i);i=a[i].f)stack[++top]=a[i].f;
while(top)pushdown(stack[top--]);
while(!isroot(rt)){
int x=a[rt].f,y=a[x].f;
if(!isroot(x)){
if((a[y].son[0]==x)^(a[x].son[0]==rt))turn(rt);
else turn(x);
}
turn(rt);
}
}
void access(int rt){
for(int i=0;rt;i=rt,rt=a[rt].f){
splay(rt);
a[rt].son[1]=i;
pushup(rt);
}
}
inline void makeroot(int rt){access(rt);splay(rt);a[rt].flag^=1;}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}
inline void link(int x,int y){makeroot(x);a[x].f=y;}
inline void query(int x,int y,int &p,int &q){
split(x,y);
p=a[y].v_one;q=a[y].v_two;
}
}
inline bool cmp(const Graph &p,const Graph &q){
return p.w<q.w;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void uniun(int x,int y){x=find(x);y=find(y);if(x!=y)fa[y]=x;}
void kruskal(){
long long sum=0,ans=MAX;
for(int i=1;i<=m;i++){
int u=a[i].u,v=a[i].v;
if(find(u)!=find(v)){
uniun(u,v);
sum+=a[i].w;
LCT::a[i+n].v=LCT::a[i+n].v_one=a[i].w;
LCT::link(u,i+n);
LCT::link(v,i+n);
}
else{
int p,q;
LCT::query(u,v,p,q);
ans=min(ans,(long long)a[i].w-(a[i].w>p?p:q));
}
}
printf("%lld\n",ans+sum);
}
void init(){
n=read();m=read();
for(int i=1;i<=m;i++){a[i].u=read();a[i].v=read();a[i].w=read();}
for(int i=1;i<=n;i++)fa[i]=i;
sort(a+1,a+m+1,cmp);
}
int main(){
init();
kruskal();
return 0;
}
```