Eternity

Until The End

Kruskal重构树

发表于 分类于 ，
本文字数： 6k 阅读时长 ≈ 5 分钟

“自命之神人，敢于直面第二次的，重启人生。”

Kruskal 算法

首先复习一下最小生成树的算法——$\text{Kruskal}$ ，是一种基于贪心的最小生成树算法，在最短路领域相当于 $\text{Spfa}$ ，但虽然很少被卡，总体思路在于维护一个并查集，并以权值排序枚举边，并以此加边构成一张图的最小生成树，无解情况在于 $m<n-1$ 或者图不连通，代码极其简洁：

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
struct Edges
{
    int u,v,val;
    bool operator<(const Edges &x) const
    {
        return val<x.val;
    }
}Ed[MAXM<<1];
int res,Rt[MAXN],cnt
int main()
{
    //init
    std::sort(Ed+1,Ed+M+1);
    for(int i=1;i<=M;++i)
    {
        auto e=Ed[i];
        e.u=getRt(e.u),e.v=getRt(e.v);
        if(Rt[e.u]!=Rt[e.v])
        {
            Rt[e.u]=e.v;
            res+=e.val,++cnt;
        }
        if(cnt==N-1)
        {
            write(res);
            return 0;
        }
    }
    write("No Solution!");
    return 0;
}

这是一种普及选手都需要学习的算法，时间复杂度 $\mathcal O(m\log m)$ 。

重构树

所谓重构树，大概意思是指，对于一张图，我们重构这张图使其成为一棵二叉树，这棵二叉树有 $n$ 个叶结点，对应原来图的 $n$ 个结点。

然后这样构造出来的树并没有什么特点，因为我们并不知道如何去连接两个叶结点，合并集合。然后就随便搞一个算法给它怼上去，直到使用 $\text{Kruskal}$ 。

依然选择从小到大枚举边权，依然选择连接 $(u,v,val)$ ，如果当前 $u,v$ 未连通，则构建一个结点 $f$ ，表示为 $u,v$ 的父结点，其点权为 $val$ 。然后依次向上，会发现，因为我们按照贪心思路由小到大，那么，对于重构树上的一条路径，从根出发，向下，点权递减。

性质

很巧妙，不会证。

  • $\text{Kruskal}$ 重构树有 $2n-1$ 个结点，$n$ 个叶结点。
  • 如果将整棵树看作堆，则重构树必然是一个堆（取决于 $\text{Kruskal}$ 的运作方式），小根堆对应最大生成树，大根堆对应最小生成树。
  • 叶结点是原图的点，非叶结点是原图的边。
  • 原图中两个结点所有简单路径的边权最大值的最小值 $=$ 最小生成树中两个结点简单路径的边权最大值 $=$ 重构树中两个结点的最近公共祖先的点权。

例题

P2245 星际迷航

曾经做过，用一种更暴力的算法，求最小生成树的最大边权，则直接把树给它建出来，然后树剖线段树查询区间最大值即可，跑到 $519ms$ ，也比较快了。

然后想想怎么重构树做出来。

上面已知了，我们只需要把重构树建出来，然后在这棵二叉树上跑 $\text{Lca}$ 找到点权即可，注意到，图并非连通，所以这其实是重构森林。

有一个性质，在于，如果像动态开点线段树那样加点的话，深度越大的点编号越小，导致我们倒序枚举点编号看当前树是否已经剖分过，第一次找到的一定是当前树的根结点，比较神仙。

然后一遍板子过去即可，记得开双倍空间，跑了 $276ms$ ，次优解。

AC 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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
const int MAXN=2e5+10,MAXM=3e5+10;
int N,M,Q,Idx,Val[MAXN];
struct G
{
    int next,to;
}Edge[MAXM<<1];
struct Edges
{
    int fr,to,val;
    bool operator<(const Edges &x) const
    {
        return val<x.val;
    }
}Ed[MAXM];
struct Dsu
{
    int Rt[MAXN];
    inline void init(int n)
    {
        for(int i=1;i<=2*n;++i) Rt[i]=i;
    }
    inline int getRt(int x)
    {
        return Rt[x]==x?x:Rt[x]=getRt(Rt[x]);
    }
    inline int merge(int x,int y)
    {
        int p=getRt(x),q=getRt(y);
        Rt[p]=Rt[q]=++Idx;
        return Idx;
    }
    inline bool connect(int x,int y)
    {
        int p=getRt(x),q=getRt(y);
        return p==q;
    }
}Dsu;
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(G){Head[u],v};Head[u]=Total;
    Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
bool Vis[MAXN];
int Fa[MAXN],Siz[MAXN],Son[MAXN],Dep[MAXN];
void dfsTree(int x,int last)
{
    Fa[x]=last,Siz[x]=Vis[x]=1,Dep[x]=Dep[last]+1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN];
void dfsChain(int x,int topf)
{
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Son[x]||v==Fa[x]) continue;
        dfsChain(v,v);
    }
}
inline int getLca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        x=Fa[Top[x]];
    }
    return Dep[x]>Dep[y]?y:x;
}
int main()
{
    read(N,M);Idx=N;
    for(int i=1;i<=M;++i) read(Ed[i].fr,Ed[i].to,Ed[i].val);
    std::sort(Ed+1,Ed+M+1);
    Dsu.init(N);
    for(int i=1;i<=M;++i)
    {
        auto e=Ed[i];
        int p1=Dsu.getRt(e.fr),p2=Dsu.getRt(e.to);
        if(p1==p2) continue;
        int lca=Dsu.merge(p1,p2);Val[lca]=e.val;
        addEdge(p1,lca),addEdge(p2,lca);
    }
    for(int i=Idx;i>=1;--i)
        if(!Vis[i])
        {
            dfsTree(i,0),
            dfsChain(i,i);
        }
    read(Q);
    for(int qx,qy;Q--;)
    {
        read(qx,qy);
        if(Dsu.connect(qx,qy)) write(Val[getLca(qx,qy)],'\n');
        else puts("impossible");
    }
    return 0;
}
/*
4 5
1 2 5
1 3 2
2 3 11
2 4 6
3 4 4
3
2 3
1 4
1 2
*/

P1967 [NOIP2013 提高组] 货车运输

双倍经验，不过求的是最大生成树，改一下 operator 即可。

AC 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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
const int MAXN=2e4+10,MAXM=5e4+10;
int N,M,Q,Idx,Val[MAXN];
struct G
{
    int next,to;
}Edge[MAXM<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(G){Head[u],v};Head[u]=Total;
    Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
struct Dsu
{
    int Rt[MAXN];
    inline void init(int n)
    {
        for(int i=1;i<=2*n;++i) Rt[i]=i;
    }
    inline int getRt(int x)
    {
        return Rt[x]==x?x:Rt[x]=getRt(Rt[x]);
    }
    inline int merge(int x,int y)
    {
        int p=getRt(x),q=getRt(y);
        Rt[p]=Rt[q]=++Idx;
        return Idx;
    }
    inline bool connect(int x,int y)
    {
        int p=getRt(x),q=getRt(y);
        return p==q;
    }
}Dsu;
struct Edges
{
    int fr,to,val;
    bool operator<(const Edges &x) const
    {
        return val>x.val;
    }
}Ed[MAXM];
inline void Kruskal()
{
    for(int i=1;i<=M;++i)
    {
        auto e=Ed[i];
        int p1=Dsu.getRt(e.fr),p2=Dsu.getRt(e.to);
        if(p1==p2) continue;
        int lca=Dsu.merge(p1,p2);Val[lca]=e.val;
        addEdge(lca,p1),addEdge(lca,p2);
    }
}
bool Vis[MAXN];
int Son[MAXN],Siz[MAXN],Dep[MAXN],Fa[MAXN];
void dfsTree(int x,int last)
{
    Dep[x]=Dep[last]+1,Siz[x]=Vis[x]=1,Fa[x]=last;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN];
void dfsChain(int x,int topf)
{
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsChain(v,v);
    }
}
inline int getLca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        x=Fa[Top[x]];
    }
    return Dep[x]>Dep[y]?y:x;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);Idx=N;
    for(int i=1;i<=M;++i) read(Ed[i].fr,Ed[i].to,Ed[i].val);
    std::sort(Ed+1,Ed+M+1);
    Dsu.init(N);
    Kruskal();
    for(int i=Idx;i>=1;--i)
        if(!Vis[i]) dfsTree(i,0),dfsChain(i,i);
    read(Q);
    for(int qx,qy;Q--;)
    {
        read(qx,qy);
        if(Dsu.connect(qx,qy)) write(Val[getLca(qx,qy)],'\n');
        else puts("-1");
    }
    return 0;
}
/*
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
*/
相关文章