2020-2021:teams:legal_string:jxm2001:圆方树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:圆方树 [2021/08/04 21:50] jxm2001 |
2020-2021:teams:legal_string:jxm2001:圆方树 [2021/08/07 20:41] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 圆方树 ====== | + | ====== 广义圆方树 ====== |
| ===== 算法简介 ===== | ===== 算法简介 ===== | ||
| 行 21: | 行 21: | ||
| <code cpp> | <code cpp> | ||
| vector<int> g[MAXN<<1]; | vector<int> g[MAXN<<1]; | ||
| - | int node_cnt; | + | int node_cnt,val[MAXN<<1]; |
| - | int low[MAXN],dfs_id[MAXN],dfs_t,bcc_id[MAXN],bcc_cnt; | + | int low[MAXN],dfs_id[MAXN],dfs_t,bcc_cnt; |
| vector<int> bcc[MAXN]; | vector<int> bcc[MAXN]; | ||
| - | stack<pair<int,int> >Stack; | + | stack<int>Stack; |
| - | bool iscut[MAXN]; | + | |
| void dfs(int u,int fa){ | void dfs(int u,int fa){ | ||
| low[u]=dfs_id[u]=++dfs_t; | low[u]=dfs_id[u]=++dfs_t; | ||
| - | blk_sz++; | + | Stack.push(u); |
| - | int child=0; | + | |
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| int v=edge[i].to; | int v=edge[i].to; | ||
| if(v==fa)continue; | if(v==fa)continue; | ||
| if(!dfs_id[v]){ | if(!dfs_id[v]){ | ||
| - | Stack.push(make_pair(u,v)); | ||
| dfs(v,u); | dfs(v,u); | ||
| low[u]=min(low[u],low[v]); | low[u]=min(low[u],low[v]); | ||
| if(low[v]>=dfs_id[u]){ | if(low[v]>=dfs_id[u]){ | ||
| - | iscut[u]=true; | ||
| - | pair<int,int> temp; | ||
| bcc[++bcc_cnt].clear(); | bcc[++bcc_cnt].clear(); | ||
| while(true){ | while(true){ | ||
| - | temp=Stack.top();Stack.pop(); | + | int temp=Stack.top();Stack.pop(); |
| - | if(bcc_id[temp.first]!=bcc_cnt){ | + | bcc[bcc_cnt].push_back(temp); |
| - | bcc_id[temp.first]=bcc_cnt; | + | if(temp==v) |
| - | bcc[bcc_cnt].push_back(temp.first); | + | |
| - | } | + | |
| - | if(bcc_id[temp.second]!=bcc_cnt){ | + | |
| - | bcc_id[temp.second]=bcc_cnt; | + | |
| - | bcc[bcc_cnt].push_back(temp.second); | + | |
| - | } | + | |
| - | if(temp.first==u&&temp.second==v) | + | |
| break; | break; | ||
| } | } | ||
| - | node_cnt++;//就加了几行 | + | bcc[bcc_cnt].push_back(u); |
| for(int node_id:bcc[bcc_cnt]){ | for(int node_id:bcc[bcc_cnt]){ | ||
| g[node_cnt].push_back(node_id); | g[node_cnt].push_back(node_id); | ||
| 行 60: | 行 48: | ||
| } | } | ||
| } | } | ||
| - | child++; | ||
| - | } | ||
| - | else if(dfs_id[v]<dfs_id[u]){ | ||
| - | Stack.push(make_pair(u,v)); | ||
| - | low[u]=min(low[u],dfs_id[v]); | ||
| } | } | ||
| + | else if(dfs_id[v]<dfs_id[u]) | ||
| + | low[u]=min(low[u],dfs_id[v]); | ||
| } | } | ||
| - | if(u==fa&&child<2) | ||
| - | iscut[u]=false; | ||
| } | } | ||
| - | void find_bcc(int n){ | + | void build_tree(int n){ |
| mem(dfs_id,0); | mem(dfs_id,0); | ||
| - | mem(iscut,0); | ||
| - | mem(bcc_id,0); | ||
| dfs_t=bcc_cnt=0; | dfs_t=bcc_cnt=0; | ||
| node_cnt=n; | node_cnt=n; | ||
| _rep(i,1,n){ | _rep(i,1,n){ | ||
| - | if(!dfs_id[i]) | + | if(!dfs_id[i]){ |
| - | dfs(i,i); | + | dfs(i,i); |
| + | Stack.pop();//别忘了清空根节点 | ||
| + | } | ||
| } | } | ||
| } | } | ||
| 行 118: | 行 101: | ||
| vector<int> g[MAXN<<1]; | vector<int> g[MAXN<<1]; | ||
| int node_cnt,blk_sz,val[MAXN<<1]; | int node_cnt,blk_sz,val[MAXN<<1]; | ||
| - | int low[MAXN],dfs_id[MAXN],dfs_t,bcc_id[MAXN],bcc_cnt; | + | int low[MAXN],dfs_id[MAXN],dfs_t,bcc_cnt; |
| vector<int> bcc[MAXN]; | vector<int> bcc[MAXN]; | ||
| - | stack<pair<int,int> >Stack; | + | stack<int>Stack; |
| - | bool iscut[MAXN]; | + | |
| void dfs(int u,int fa){ | void dfs(int u,int fa){ | ||
| low[u]=dfs_id[u]=++dfs_t; | low[u]=dfs_id[u]=++dfs_t; | ||
| blk_sz++; | blk_sz++; | ||
| - | int child=0; | + | Stack.push(u); |
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| int v=edge[i].to; | int v=edge[i].to; | ||
| if(v==fa)continue; | if(v==fa)continue; | ||
| if(!dfs_id[v]){ | if(!dfs_id[v]){ | ||
| - | Stack.push(make_pair(u,v)); | ||
| dfs(v,u); | dfs(v,u); | ||
| low[u]=min(low[u],low[v]); | low[u]=min(low[u],low[v]); | ||
| if(low[v]>=dfs_id[u]){ | if(low[v]>=dfs_id[u]){ | ||
| - | iscut[u]=true; | ||
| - | pair<int,int> temp; | ||
| bcc[++bcc_cnt].clear(); | bcc[++bcc_cnt].clear(); | ||
| while(true){ | while(true){ | ||
| - | temp=Stack.top();Stack.pop(); | + | int temp=Stack.top();Stack.pop(); |
| - | if(bcc_id[temp.first]!=bcc_cnt){ | + | bcc[bcc_cnt].push_back(temp); |
| - | bcc_id[temp.first]=bcc_cnt; | + | if(temp==v) |
| - | bcc[bcc_cnt].push_back(temp.first); | + | |
| - | } | + | |
| - | if(bcc_id[temp.second]!=bcc_cnt){ | + | |
| - | bcc_id[temp.second]=bcc_cnt; | + | |
| - | bcc[bcc_cnt].push_back(temp.second); | + | |
| - | } | + | |
| - | if(temp.first==u&&temp.second==v) | + | |
| break; | break; | ||
| } | } | ||
| + | bcc[bcc_cnt].push_back(u); | ||
| val[++node_cnt]=bcc[bcc_cnt].size(); | val[++node_cnt]=bcc[bcc_cnt].size(); | ||
| for(int node_id:bcc[bcc_cnt]){ | for(int node_id:bcc[bcc_cnt]){ | ||
| 行 156: | 行 129: | ||
| } | } | ||
| } | } | ||
| - | child++; | ||
| - | } | ||
| - | else if(dfs_id[v]<dfs_id[u]){ | ||
| - | Stack.push(make_pair(u,v)); | ||
| - | low[u]=min(low[u],dfs_id[v]); | ||
| } | } | ||
| + | else if(dfs_id[v]<dfs_id[u]) | ||
| + | low[u]=min(low[u],dfs_id[v]); | ||
| } | } | ||
| - | if(u==fa&&child<2) | ||
| - | iscut[u]=false; | ||
| } | } | ||
| int sz[MAXN<<1]; | int sz[MAXN<<1]; | ||
| 行 181: | 行 149: | ||
| blk_sz=0; | blk_sz=0; | ||
| dfs(rt,rt); | dfs(rt,rt); | ||
| + | Stack.pop(); | ||
| dfs2(rt,rt); | dfs2(rt,rt); | ||
| } | } | ||
| - | void find_bcc(int n){ | + | void build_tree(int n){ |
| mem(dfs_id,0); | mem(dfs_id,0); | ||
| - | mem(iscut,0); | ||
| - | mem(bcc_id,0); | ||
| dfs_t=bcc_cnt=0; | dfs_t=bcc_cnt=0; | ||
| node_cnt=n; | node_cnt=n; | ||
| 行 203: | 行 170: | ||
| Insert(v,u); | Insert(v,u); | ||
| } | } | ||
| - | find_bcc(n); | + | build_tree(n); |
| enter(ans); | enter(ans); | ||
| return 0; | return 0; | ||
| 行 366: | 行 333: | ||
| } | } | ||
| int node_cnt; | int node_cnt; | ||
| - | int low[MAXN],dfs_id[MAXN],dfs_t,bcc_id[MAXN],bcc_cnt; | + | int low[MAXN],dfs_id[MAXN],dfs_t,bcc_cnt; |
| vector<int> bcc[MAXN]; | vector<int> bcc[MAXN]; | ||
| - | stack<pair<int,int> >Stack; | + | stack<int>Stack; |
| void dfs(int u,int fa){ | void dfs(int u,int fa){ | ||
| low[u]=dfs_id[u]=++dfs_t; | low[u]=dfs_id[u]=++dfs_t; | ||
| + | Stack.push(u); | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| int v=edge[i].to; | int v=edge[i].to; | ||
| if(v==fa)continue; | if(v==fa)continue; | ||
| if(!dfs_id[v]){ | if(!dfs_id[v]){ | ||
| - | Stack.push(make_pair(u,v)); | ||
| dfs(v,u); | dfs(v,u); | ||
| low[u]=min(low[u],low[v]); | low[u]=min(low[u],low[v]); | ||
| if(low[v]>=dfs_id[u]){ | if(low[v]>=dfs_id[u]){ | ||
| - | pair<int,int> temp; | ||
| bcc[++bcc_cnt].clear(); | bcc[++bcc_cnt].clear(); | ||
| while(true){ | while(true){ | ||
| - | temp=Stack.top();Stack.pop(); | + | int temp=Stack.top();Stack.pop(); |
| - | if(bcc_id[temp.first]!=bcc_cnt){ | + | bcc[bcc_cnt].push_back(temp); |
| - | bcc_id[temp.first]=bcc_cnt; | + | if(temp==v) |
| - | bcc[bcc_cnt].push_back(temp.first); | + | |
| - | } | + | |
| - | if(bcc_id[temp.second]!=bcc_cnt){ | + | |
| - | bcc_id[temp.second]=bcc_cnt; | + | |
| - | bcc[bcc_cnt].push_back(temp.second); | + | |
| - | } | + | |
| - | if(temp.first==u&&temp.second==v) | + | |
| break; | break; | ||
| } | } | ||
| + | bcc[bcc_cnt].push_back(u); | ||
| node_cnt++; | node_cnt++; | ||
| for(int node_id:bcc[bcc_cnt]){ | for(int node_id:bcc[bcc_cnt]){ | ||
| 行 401: | 行 361: | ||
| } | } | ||
| } | } | ||
| - | else if(dfs_id[v]<dfs_id[u]){ | + | else if(dfs_id[v]<dfs_id[u]) |
| - | Stack.push(make_pair(u,v)); | + | low[u]=min(low[u],dfs_id[v]); |
| - | low[u]=min(low[u],dfs_id[v]); | + | |
| - | } | + | |
| } | } | ||
| } | } | ||
| 行 418: | 行 376: | ||
| node_cnt=n; | node_cnt=n; | ||
| dfs(1,1); | dfs(1,1); | ||
| + | Stack.pop(); | ||
| Tree::build(n); | Tree::build(n); | ||
| while(q--){ | while(q--){ | ||
| 行 599: | 行 558: | ||
| while(T--){ | while(T--){ | ||
| solve(); | solve(); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ====== 狭义圆方树 ====== | ||
| + | |||
| + | ===== 算法简介 ===== | ||
| + | |||
| + | 一种应用于仙人掌图的特殊圆方树。其中，定义仙人掌一类连通图，图中每条边至多出现在一个环中。 | ||
| + | |||
| + | ===== 算法实现 ===== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P5236|洛谷p5236]] | ||
| + | |||
| + | 与广义圆方树的唯一区别在于狭义圆方树不存在大小为 $2$ 的双连通分量。 | ||
| + | |||
| + | 这样，该图的所有连通分量大小至少为 $3$，且一定构成环。每个方点一定与圆点连边，但圆点也可能与圆点连边。 | ||
| + | |||
| + | 由于仙人掌的特殊性，可以用圆方树求图中任意两点最短路。其中，对于大小为 $2$ 的连通分量，不添加方点，两圆点直接连边。 | ||
| + | |||
| + | 对大小超过 $2$ 的连通分量，新建一个方点，每个点向方点连边，边权为该点到确立该连通分量的割点的环上最短距离。 | ||
| + | |||
| + | 同时每个圆点也记录该点到确立该连通分量的割点的 $\text{Tarjan}$ 树上距离，每个方点记录环的总长度。 | ||
| + | |||
| + | 查询时，如果两点 $\text{LCA}$ 为圆点，则答案就是最短距离。否则两个点先跳到 $\text{LCA}$ 的儿子，然后根据儿子点权和方点点权计算距离。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e4+5,MAXM=2e4+5; | ||
| + | const int MAXN2=MAXN<<1; | ||
| + | struct Edge{ | ||
| + | int to,w,next; | ||
| + | }; | ||
| + | namespace Tree{ | ||
| + | Edge edge[MAXN2<<1]; | ||
| + | int n,head[MAXN2],edge_cnt,val[MAXN2]; | ||
| + | void Insert(int u,int v,int w){ | ||
| + | edge[++edge_cnt]=Edge{v,w,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int d[MAXN2],sz[MAXN2],f[MAXN2],dfs_id[MAXN2],dfs_t; | ||
| + | int h_son[MAXN2],mson[MAXN2],p[MAXN2]; | ||
| + | LL dis[MAXN2]; | ||
| + | void dfs_1(int u,int fa,int depth){ | ||
| + | sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0; | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(v==fa) | ||
| + | continue; | ||
| + | dis[v]=dis[u]+edge[i].w; | ||
| + | dfs_1(v,u,depth+1); | ||
| + | sz[u]+=sz[v]; | ||
| + | if(sz[v]>mson[u]){ | ||
| + | h_son[u]=v; | ||
| + | mson[u]=sz[v]; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | void dfs_2(int u,int top){ | ||
| + | dfs_id[u]=++dfs_t;p[u]=top; | ||
| + | if(mson[u]) | ||
| + | dfs_2(h_son[u],top); | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(v==f[u]||v==h_son[u]) | ||
| + | continue; | ||
| + | dfs_2(v,v); | ||
| + | } | ||
| + | } | ||
| + | void build(int _n){ | ||
| + | n=_n; | ||
| + | dfs_1(1,0,0); | ||
| + | dfs_2(1,1); | ||
| + | } | ||
| + | int find_son(int u,int anc){ | ||
| + | int son; | ||
| + | while(p[u]!=p[anc]){ | ||
| + | son=p[u]; | ||
| + | u=f[p[u]]; | ||
| + | } | ||
| + | return u==anc?son:h_son[anc]; | ||
| + | } | ||
| + | int LCA(int u,int v){ | ||
| + | while(p[u]!=p[v]){ | ||
| + | if(d[p[u]]<d[p[v]])swap(u,v); | ||
| + | u=f[p[u]]; | ||
| + | } | ||
| + | return d[u]<d[v]?u:v; | ||
| + | } | ||
| + | int query(int u,int v){ | ||
| + | int p=LCA(u,v); | ||
| + | if(p<=n) | ||
| + | return dis[u]+dis[v]-dis[p]*2; | ||
| + | else{ | ||
| + | int p1=find_son(u,p),p2=find_son(v,p); | ||
| + | int d=min(abs(val[p1]-val[p2]),val[p]-abs(val[p1]-val[p2])); | ||
| + | return dis[u]-dis[p1]+dis[v]-dis[p2]+d; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | Edge edge[MAXM<<1]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v,int w){ | ||
| + | edge[++edge_cnt]=Edge{v,w,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int node_cnt,val[MAXN<<1]; | ||
| + | int low[MAXN],dfs_id[MAXN],f[MAXN],dfs_t,bcc_cnt; | ||
| + | LL dis[MAXN]; | ||
| + | void link(int u,int v,int w){ | ||
| + | LL s=dis[v]-dis[u]+w; | ||
| + | Tree::val[++node_cnt]=s; | ||
| + | int pos=v; | ||
| + | while(pos!=f[u]){ | ||
| + | int w2=min(dis[pos]-dis[u],s-(dis[pos]-dis[u])); | ||
| + | Tree::Insert(node_cnt,pos,w2); | ||
| + | Tree::Insert(pos,node_cnt,w2); | ||
| + | Tree::val[pos]=dis[pos]-dis[u]; | ||
| + | pos=f[pos]; | ||
| + | } | ||
| + | } | ||
| + | void dfs(int u){ | ||
| + | low[u]=dfs_id[u]=++dfs_t; | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(v==f[u])continue; | ||
| + | if(!dfs_id[v]){ | ||
| + | dis[v]=dis[u]+edge[i].w; | ||
| + | f[v]=u; | ||
| + | dfs(v); | ||
| + | low[u]=min(low[u],low[v]); | ||
| + | if(low[v]>dfs_id[u]) | ||
| + | Tree::Insert(u,v,edge[i].w); | ||
| + | } | ||
| + | else if(dfs_id[v]<dfs_id[u]) | ||
| + | low[u]=min(low[u],dfs_id[v]); | ||
| + | else | ||
| + | link(u,v,edge[i].w); | ||
| + | } | ||
| + | } | ||
| + | void build_tree(int n){ | ||
| + | mem(dfs_id,0); | ||
| + | mem(f,0); | ||
| + | dfs_t=bcc_cnt=0; | ||
| + | node_cnt=n; | ||
| + | dfs(1); | ||
| + | Tree::build(n); | ||
| + | } | ||
| + | int main(){ | ||
| + | int n=read_int(),m=read_int(),q=read_int(); | ||
| + | while(m--){ | ||
| + | int u=read_int(),v=read_int(),w=read_int(); | ||
| + | Insert(u,v,w); | ||
| + | Insert(v,u,w); | ||
| + | } | ||
| + | build_tree(n); | ||
| + | while(q--){ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | enter(Tree::query(u,v)); | ||
| } | } | ||
| return 0; | return 0; | ||
2020-2021/teams/legal_string/jxm2001/圆方树.1628085004.txt.gz · 最后更改: 2021/08/04 21:50 由 jxm2001
