LuoguP4234_最小差值生成树_LCT
题意：
给出一个无向图，求最大的边权减最小的边权最小的一棵生成树。
分析：
可以把边权从大到小排序，然后类似魔法森林那样插入。
如果两点不连通，直接连上，否则找到两点间最大的边权替换。
如果生成一棵树了就更新答案。
LCT维护边权的最大值即可。
代码：
// luogu-judger-enable-o2
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 400050
#define M 200050
#define ls ch[p][0]
#define rs ch[p][1]
#define get(x) (ch[f[x]][1]==x)
struct A {
int x,y,v;
}a[N];
bool cmp(const A &x,const A &y){return x.v>y.v;}
int ch[N][2],f[N],val[N],siz[N],rev[N],mx[N],tot,n,m,kill[M];
inline bool isrt(int p) {
return ch[f[p]][1]!=p&&ch[f[p]][0]!=p;
}
inline void pushup(int p) {
mx[p]=p;
if(val[mx[ls]]>val[mx[p]]) mx[p]=mx[ls];
if(val[mx[rs]]>val[mx[p]]) mx[p]=mx[rs];
}
inline void pushdown(int p) {
if(rev[p]) {
swap(ch[ls][0],ch[ls][1]);
swap(ch[rs][0],ch[rs][1]);
rev[ls]^=1; rev[rs]^=1;
rev[p]=0;
}
}
void update(int p) {
if(!isrt(p)) update(f[p]);
pushdown(p);
}
void rotate(int x) {
int y=f[x],z=f[y],k=get(x);
if(!isrt(y)) ch[z][ch[z][1]==y]=x;
ch[y][k]=ch[x][!k]; f[ch[y][k]]=y;
ch[x][!k]=y; f[y]=x; f[x]=z;
pushup(y); pushup(x);
}
void splay(int x) {
update(x);
for(int fa;fa=f[x],!isrt(x);rotate(x))
if(!isrt(fa))
rotate(get(x)==get(fa)?fa:x);
}
void access(int p) {
int t=0;
while(p) {
splay(p);
rs=t;
pushup(p);
t=p;
p=f[p];
}
}
void makeroot(int p) {
access(p); splay(p);
swap(ls,rs); rev[p]^=1;
}
void link(int x,int p) {
makeroot(x); splay(p); f[x]=p;
}
void cut(int x,int p) {
makeroot(x); access(p); splay(p); ls=f[x]=0;
}
int find(int p) {
access(p); splay(p);
while(ls) pushdown(p),p=ls;
return p;
}
int query(int x,int p) {
makeroot(x); access(p); splay(p); return mx[p];
}
int now=1;
int calc() {
while(kill[now]&&now<=m) now++;
return a[now].v;
}
int main() {
int ans=1<<30;
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;i++) mx[i]=i;
for(i=1;i<=m;i++) {
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
}
sort(a+1,a+m+1,cmp);
tot=n;
int ne=0;
for(i=1;i<=m;i++) {
int x=a[i].x,y=a[i].y;
tot++;
if(x==y) {
kill[i]=1;
continue;
}
int dx=find(x),dy=find(y);
if(dx!=dy) {
ne++;
val[tot]=a[i].v; mx[tot]=tot; link(x,tot); link(tot,y);
}else {
int k=query(x,y);
kill[k-n]=1;
// printf("%d %d %d\n",k,a[k-n].x,a[k-n].y);
cut(a[k-n].x,k); cut(k,a[k-n].y);
val[tot]=a[i].v; mx[tot]=tot; link(x,tot); link(tot,y);
}
if(ne==n-1) {
ans=min(ans,calc()-a[i].v);
}
}
printf("%d\n",ans);
}