LCT求解最小生成树
前言
最小生成树模板: P3366 【模板】最小生成树
朴素的kruskal为主流最小生成树算法
而LCT(link cut tree)也是可以维护最小生成树的
由于LCT动态维护最小生成树,加上常数较大
在实际测试中比kruskal慢了很多倍
最小生成树
维护结点的连通性 可以看看这个
显然我们不是把它和kruskal连用,那样反倒变成了 $\log^2$ 的劣解了
而LCT它是动态的,因此难以使用树链剖分的做法,将边权映射到点权上
那么我们可以把通过建“边点”将边权转化为点权
所谓的边点指直接将每条边当做点,那么连边的操作就变成了
w[idx+n]=z; // 记录边权 ,idx = 1 to m
link(x,idx+n),link(idx+n,y); // 和边所连接的两结点与该边所建结点相连
因为没有对边权排序,那如果 x,y
已经连通怎么办呢?
由于x,y
都在LCT上,因此我们可以维护它们所成的链中最大的那一条边
如果当前处理到的边比那条边边权更小,就可以将那条极大边断掉
如何断边?直接t[t[now].ch[0]].fa=t[t[now].ch[1]].fa=0
即可
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define N (int)(4e5+5)
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n,m,idx,ans,cnt;
namespace LCT
{
struct node
{
int ch[2],w,id,fa,sz,mx,tag;
}t[N];
#define isroot(x) ((t[t[x].fa].ch[0]!=x)&&(t[t[x].fa].ch[1]!=x))
void pushr(int x)
{
swap(t[x].ch[0],t[x].ch[1]);
t[x].tag^=1;
}
void push_up(int x)
{
t[x].id=x;t[x].mx=t[x].w;
if(t[t[x].ch[0]].mx>t[x].mx)
t[x].mx=t[t[x].ch[0]].mx,t[x].id=t[t[x].ch[0]].id;
if(t[t[x].ch[1]].mx>t[x].mx)
t[x].mx=t[t[x].ch[1]].mx,t[x].id=t[t[x].ch[1]].id;
}
void push_down(int x)
{
if(t[x].tag)
{
if(t[x].ch[0])pushr(t[x].ch[0]);
if(t[x].ch[1])pushr(t[x].ch[1]);
t[x].tag=0;
}
}
void push_all(int x)
{
if(!isroot(x))push_all(t[x].fa);
push_down(x);
}
void rotate(int x)
{
int y=t[x].fa;
int z=t[y].fa;
int k=t[y].ch[1]==x;
if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;
t[x].fa=z;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].fa=y;
t[x].ch[k^1]=y;
t[y].fa=x;
push_up(y);
push_up(x);
}
void splay(int x)
{
push_all(x);
while(!isroot(x))
{
int y=t[x].fa;
int z=t[y].fa;
if(!isroot(y))
(t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);
rotate(x);
}
}
void access(int x)
{
for(int y=0; x; y=x,x=t[x].fa)
splay(x),t[x].ch[1]=y,push_up(x);
}
void make_root(int x)
{
access(x);splay(x);
pushr(x);
}
int find_root(int x)
{
access(x);splay(x);
while(t[x].ch[0])push_down(x),x=t[x].ch[0];
splay(x);
return x;
}
void split(int x,int y)
{
make_root(x);
access(y);splay(y);
}
void link(int x,int y)
{
make_root(x);
if(find_root(y)!=x)t[x].fa=y;
}
int ck(int x,int y)
{
make_root(x);
return find_root(y)!=x;
}
/*
void cut(int x,int y)
{
make_root(x);
if(find_root(y)==x&&t[y].fa==x&&!t[y].ch[0])
{
t[x].ch[1]=t[y].fa=0;
push_up(x);
}
}
*/
}
signed main()
{
using namespace LCT;
read(n);read(m);
idx=n;
for(int i=1,x,y,z; i<=m; i++)
{
read(x);read(y);read(z);
t[++idx].w=z;
if(x!=y&&ck(x,y))link(x,idx),link(idx,y),ans+=z,++cnt;
else
{
split(x,y);int now=t[y].id;
if(t[now].mx<=z)continue;
ans-=t[now].mx-z;splay(now);
t[t[now].ch[0]].fa=t[t[now].ch[1]].fa=0;
link(x,idx);link(idx,y);
}
}
if(cnt<n-1)puts("orz");
else write(ans),pc('\n');
return 0;
}
这敲代码多是一件美逝啊