「Luogu 4234」最小差值生成树

发表于 | | 阅读次数:
字数统计: 868 字

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%