抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

圆方树学习笔记

发布于：2019年7月31日

圆方树这个东西咕了好久都没学，今天一看还是比较简单的

先讲一下仙人掌的定义：任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

放几张图：

え、 放错了，不过还是比较形象的（估计就是仙人掌名字的又来吧）：

放一个真·仙人掌：

fromBZOJ1023\rm from BZOJ 1023

我自己画的仙人掌图：

考虑解决仙人掌上面问题，上面的环很讨厌，我们要想一种办法把环缩掉。

当然不能直接上tarjan\rm tarjan缩环，因为tarjan\rm tarjan会把很多性质破坏掉，比如两点之间距离之类。

考虑把环缩成菊花图：

我们叫原来仙人掌上面的点圆点，新加进的菊花图的中心节点为方点，这样形成一棵圆方树。

（其实圆方树就是这样一个简单的东西，把环萎♂进去形成一个菊花图，网上的很多题解都写复杂了）

为什么不是仙人掌不能建立圆方树？考虑这样一个图：

把它的（伪）圆方树建出来，变成介个样子：

发现这并不是一棵树，因为有环。造成这个环的本质是有一条边在两个环上面都出现了一次。

专业一点来说，对于一条边<u,v><u,v>，设它同时存在两个环建立出的两个菊花图的中心节点为s1,s2s_1,s_2，那么必有u−s1−v−s2u-s_1-v-s_2这个环。

按照边数排个序：非联通图<<树（其实是仙人掌）<<基环树（其实也是仙人掌）≤\le仙人掌≤\le非仙人掌的连通图

讲完定义之后，我们来看怎么实现：

静态仙人掌

P5236 【模板】静态仙人掌

仙人掌图上面求节点uu，vv之间最短路dd。

先建好一棵圆方树（tarjan\rm tarjan实现）：

考虑第一件事，上面标红的那些边边权怎么弄，才不能破坏最短路的性质，也就是说，从红色边上面走相当于从环上面走。

考虑先钦定一个环上面的点albalb，我们强制经过albalb，所以从uu到vv相当于u−alb−vu-alb-v

具体实现的时候，记录一个sumsum代表边权的前缀和。

考虑第二件事，如何查询两个节点之间最短路？

设lcalca为LCA(u,v)LCA(u,v)

1.1.lcalca为圆点：dd为树上uu，vv之间距离，即d=dis(u,v)d=dis(u,v)

2.2.lcalca为方点：较为复杂，因为方点连出的边不存在，所以不能直接像上面一样搞，设lcalca的儿子中为uu，vv两个节点的祖先的两个节点为aa，bb，这样说有些复杂，不妨画图理解。

如图，lcalca往aa，bb连的两条边是不存在的，所以不能经过，所以只能从uu向上跳到aa，然后在环上面走一段路程到bb，最后从bb往下跳到vv，所以d=dis(u,a)+dis(a,b)+dis(b,v)d=dis(u,a)+dis(a,b)+dis(b,v)

注意：在环上面走有两种走法，不能忘记

实现起来还是有点细节的。

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
#define MAXN 40005
#define MAXM 23
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
struct Edge{
    int to,len;
};
vector<Edge>G1[MAXN],G2[MAXN];//G1为原图，G2为圆方树
inline void _AddEdge1(int u,int v,int w){
    G1[u].push_back(Edge{v,w});
}
inline void AddEdge1(int u,int v,int w){
    _AddEdge1(u,v,w),_AddEdge1(v,u,w);
}
inline void _AddEdge2(int u,int v,int w){
    G2[u].push_back(Edge{v,w});
}
inline void AddEdge2(int u,int v,int w){
    _AddEdge2(u,v,w),_AddEdge2(v,u,w);
}
namespace Lca{
    int anc[MAXN][MAXM],dis[MAXN],dep[MAXN];
    void dfs(int u,int father){
        anc[u][0]=father;
        for (register int i=1;i<MAXM;++i){
            anc[u][i]=anc[anc[u][i-1]][i-1];
        }
        for (register int i=0;i<G2[u].size();++i){
            int v=G2[u][i].to,w=G2[u][i].len;
            if (v!=father){
                dep[v]=dep[u]+1;
                dis[v]=dis[u]+w;
                dfs(v,u);
            }
        }
    }
    inline int LCA(int u,int v){
        if (dep[u]<dep[v]) swap(u,v);
        for (register int i=MAXM-1;i>=0;--i){
            if (dep[anc[u][i]]>=dep[v]){
                u=anc[u][i];
            }
        }
        if (u==v){
            return v;
        }
        for (register int i=MAXM-1;i>=0;--i){
            if (anc[u][i]!=anc[v][i]){
                u=anc[u][i];
                v=anc[v][i];
            }
        }
        return anc[u][0];
    }
    inline int Jump(int u,int lca){//H♂p
        for (register int i=MAXM-1;i>=0;--i){
            if (dep[anc[u][i]]>dep[lca]){
                u=anc[u][i];
            }
        }
        return u;
    }
    inline int Dis(int u,int v){
        return dis[u]+dis[v]-dis[LCA(u,v)]*2;
    }
}
using namespace Lca;
int square;//方点
int sum[MAXN];//一个类似于前缀和的东西，求环上边权的时候可以方便地相减得出答案
namespace RS_Tree{//Round Square Tree ???
    int dfn[MAXN],low[MAXN],cnt,fa[MAXN],tofa[MAXN];
    void tarjan(int u,int father){
        dfn[u]=low[u]=++cnt;
        for (register int i=0;i<G1[u].size();++i){
            int v=G1[u][i].to,w=G1[u][i].len;
            if (v!=father){
                if (!dfn[v]){fa[v]=u;tofa[v]=w;tarjan(v,u);low[u]=min(low[u],low[v]);}
                else{low[u]=min(low[u],dfn[v]);}
                if (low[v]<=dfn[u]) continue;
                AddEdge2(u,v,w);//原来的仙人掌上面边不在环里面的边要保留
            }
        }
        for (register int i=0;i<G1[u].size();++i){
            int v=G1[u][i].to;
            if (fa[v]==u||dfn[v]<=dfn[u]) continue;
            //找到非树边
            ++square;//新建方点
            int s=G1[u][i].len,t=v;
            while (t!=fa[u]){//在环上面绕圈圈
                sum[t]=s;
                s+=tofa[t];
                t=fa[t];
            }
            sum[square]=sum[u];sum[u]=0;
            //求出整个圈上面边权之和，u多算了，所以设成0
            //为什么记录sum[square]哪？往下看
            t=v;
            while (t!=fa[u]){
                AddEdge2(t,square,min(sum[t],sum[square]-sum[t]));//加上不存在的边
                //其实就是把环上走的一大堆路程压到一条边上面
                //可以往前面绕，也可以后面绕，所以取一个min
                t=fa[t];
            }
        }
    }
}
using namespace RS_Tree;
int n,m;
int main(){
    n=read(),m=read();
    int q=read();
    for (register int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        AddEdge1(u,v,w);
    }
    square=n;
    tarjan(1,0);
    dfs(1,1);
    while (q--){
        int u=read(),v=read();
        int lca=LCA(u,v);
        if (lca<=n){//圆点
            printf("%d\n",Dis(u,v));
        }
        else {//方点
            int A=Jump(u,lca),B=Jump(v,lca);//前面说的a,b
            int ans=Dis(u,A)+Dis(B,v);
            if (sum[A]<sum[B]) swap(A,B);//避免负数（不知道alb在A,B的哪里）
            printf("%d\n",ans+min(sum[A]-sum[B],sum[lca]+sum[B]-sum[A]));
            //直接调用sum[lca]体现出记录sum[square]的好处
        }
    }
}

倍增写的，跑的比较慢。

咕咕

（我连LCT都不会哪）

相关文章
LOJ #10097. 「一本通 3.5 练习 5」和平委员会基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/218474d4.html

更新于：2022年6月14日

tarjan

仙人掌

圆方树

评论