「Luogu 4234」最小差值生成树

Description

题目链接:Luogu 4234

给定一个标号为从 $1$ 到 $n$ 的、有 $m$ 条边的无向图,求边权最大值与最小值的差值最小的生成树。

数据范围:$1\le n\le 5\times 10^4$,$1\le m\le 2\times 10^5$,$1\le w_i\le 10^4$


Solution

肯定要先贪心地把边按照权值从小到大排序,然后依次加入树中。假设当前的边为 $(u,v,w)$,此时有 $2$ 种情况:

  • 当 $u$ 和 $v$ 不连通:我们直接将 $(u,v,w)$ 加入树中。
  • 当 $u$ 和 $v$ 联通时:如果我们直接加入必然会形成一个环,那么我们现将链 $(u,v)$ 上权值最小的边删除,然后加入 $(u,v,w)$ 这条边。

按照这样的操作得到的答案一定是最优的。注意到我们有动态加边和删边,那么可以用 $\text{LCT}$ 维护。

考虑如何求答案。我们维护一个指针 $p​$ 指向树中权值最小的边。每次加入的边一定是树中权值最大的。一旦树联通了就更新答案。

注意:本题没有保证无自环,需要忽略自环

时间复杂度:$O(m\log m)$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <cstdio>
#include <algorithm>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]

const int N=2.5e5+5;
int n,m,f[N],fa[N],ch[N][2],mn[N],idx[N],st[N];
bool vis[N],r[N];
struct Edge {
int u,v,w;
bool operator < (const Edge &b)const {
return w<b.w;
}
} e[N];

bool get(int x) {
return rs(fa[x])==x;
}
bool isroot(int x) {
return ls(fa[x])!=x&&rs(fa[x])!=x;
}
void rev(int x) {
r[x]^=1,std::swap(ls(x),rs(x));
}
void pushup(int x) {
mn[x]=idx[x];
if(ls(x)&&e[mn[ls(x)]].w<e[mn[x]].w) mn[x]=mn[ls(x)];
if(rs(x)&&e[mn[rs(x)]].w<e[mn[x]].w) mn[x]=mn[rs(x)];
}
void pushdown(int x) {
if(r[x]) rev(ls(x)),rev(rs(x)),r[x]=0;
}
void rotate(int x) {
int y=fa[x],z=fa[y],k=get(x);
!isroot(y)&&(ch[z][get(y)]=x),fa[x]=z;
ch[y][k]=ch[x][!k],fa[ch[x][!k]]=y;
ch[x][!k]=y,fa[y]=x;
pushup(y),pushup(x);
}
void splay(int x) {
int u=x,tp=0;
st[++tp]=u;
while(!isroot(u)) st[++tp]=u=fa[u];
while(tp) pushdown(st[tp--]);
while(!isroot(x)) {
int y=fa[x];
if(!isroot(y)) rotate(get(x)==get(y)?y:x);
rotate(x);
}
}
void access(int x) {
for(int y=0;x;x=fa[y=x]) splay(x),rs(x)=y,pushup(x);
}
void makeroot(int x) {
access(x),splay(x),rev(x);
}
void split(int x,int y) {
makeroot(x),access(y),splay(y);
}
void link(int x,int y) {
makeroot(x),fa[x]=y;
}
void cut(int x,int y) {
split(x,y),fa[x]=ls(y)=0,pushup(y);
}
int find(int x) {
return f[x]==x?x:f[x]=find(f[x]);
}
int main() {
scanf("%d%d",&n,&m);
e[0].w=1<<30;
for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
for(int i=1;i<=n+m;++i) i<=n?f[i]=i:idx[i]=i-n;
std::sort(e+1,e+m+1);
int ans=1<<30;
for(int cnt=0,p=1,i=1;i<=m;++i) {
int u=e[i].u,v=e[i].v;
if(u==v) continue;
if(find(u)==find(v)) {
split(u,v);
int j=mn[v];
cut(e[j].u,j+n),cut(e[j].v,j+n),vis[j]=0;
link(u,i+n),link(v,i+n),vis[i]=1;
while(!vis[p]) ++p;
} else {
f[find(u)]=find(v);
link(u,i+n),link(v,i+n),vis[i]=1,++cnt;
}
if(cnt==n-1) ans=std::min(ans,e[i].w-e[p].w);
}
printf("%d\n",ans);
return 0;
}
0%