前言

最小生成树模板： P3366 【模板】最小生成树

朴素的kruskal为主流最小生成树算法

而LCT(link cut tree)也是可以维护最小生成树的

由于LCT动态维护最小生成树，加上常数较大

在实际测试中比kruskal慢了很多倍

LCT求解最小生成树

维护结点的连通性 可以看看这个

显然我们不是把它和kruskal连用，那样反倒变成了 log⁡2\log^2log2 的劣解了

而LCT它是动态的，因此难以使用树链剖分的做法，将边权映射到点权上

那么我们可以把通过建“边点”将边权转化为点权

所谓的边点指直接将每条边当做点，那么连边的操作就变成了

w[idx+n]=z; // 记录边权 ,idx = 1 to mlink(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;}

这敲代码多是一件美逝啊

转载请说明出处