差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:圆方树 [2021/08/07 19:56]
jxm2001 [算法实现]
+++ 2020-2021:teams:legal_string:jxm2001:圆方树 [2021/08/07 20:41] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-====== 圆方树 ======
+====== 广义圆方树 ======
 ===== 算法简介 =====
@@ 行 558: / 行 558: @@
 	while(T--){
 		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;

CVBB ACM Team

用户工具

站点工具

差别

页面工具