首页 > 其他分享 >圆方树

圆方树

时间:2024-11-02 17:20:49浏览次数:4  
标签:ntot dfn low 圆方树 st dis

前置知识:点双连通分量

定义

圆方树:对于一个点双内的点,拆除点之间所有相连的边,并和一个代表该点双的点连边

圆点为原图中的点,方点代表一个点双

圆方树有狭义和广义两种

狭义圆方树不把“杠铃形”当作点双,有圆圆边

广义圆方树把“杠铃形”当作点双,只有圆方边

狭义圆方树是解决仙人掌问题的利器,详见link

广义圆方树一般图都能用

建树

(模板题我在这卡了2h……)

对于仙人掌图,可以魔改tarjan,当搜到dfn[v]<dfn[x]的点时,说明一定成环,在此处直接跑环更方便(详见代码)

对于一般图,上标准的tarjan即可

代码

仙人掌图:

void tarjan(int x,int pre) {
	dfn[x]=low[x]=++index;
	st[++stpos]=x;
	erg(G,x,i) {
		int v=G.e[i].to;
		if(i==(pre^1)) continue;
		if(!dfn[v]) {
			dis[v]=dis[x]+G.e[i].dis;
			tarjan(v,i);
			low[x]=min(low[x],low[v]);
			if(low[v]>=dfn[x]) {
				if(low[v]>dfn[x]) {
					T.Addedge(x,v,G.e[i].dis);
					T.Addedge(v,x,G.e[i].dis);
				}
				while(st[stpos]!=x) stpos--;	//正常图在这里统计点双 
			}
		}
		else {
			low[x]=min(low[x],dfn[v]);
			if(low[x]!=dfn[v]) continue;
			sum[++ntot]=dis[x]-dis[v]+G.e[i].dis;	//仙人掌因为要用环的边权和sum[],在此处求更方便 
			for(int j=stpos;st[j+1]!=v;j--) {
				T.Addedge(ntot,st[j],min(dis[st[j]]-dis[v],sum[ntot]-(dis[st[j]]-dis[v])));
				T.Addedge(st[j],ntot,min(dis[st[j]]-dis[v],sum[ntot]-(dis[st[j]]-dis[v])));
			}	
		}
	}
}

细节

标签:ntot,dfn,low,圆方树,st,dis
From: https://www.cnblogs.com/zhone-lb/p/18522234

相关文章

  • abc318_g Typical Path Problem 题解 圆方树
    题目链接:https://atcoder.jp/contests/abc318/tasks/abc318_g题目大意:给出一个有\(n\)个顶点和\(m\)条边的无向连通图\(G\),没有重边和自环。顶点的编号为\(1\simn\),边的编号为\(1\simm\),第\(i\)条边连接顶点\(u_i\)和\(v_i\)。给出图上三个不同的顶点\(A,B,C......
  • 圆方树
    圆方树前置知识点双连通分量以下简称点双连通分量为点双。定义设$G=(V,E)$是一个连通无向图,$K$是$G$的点双,如果$K$中任意两点$u,v$都有路径相连,则称$K$是$G$的点双。性质两个点双最多有一个公共点,且这个点为割点。对于一个点双,它在DFS搜索树中dfn值......
  • 圆方树学习笔记
    元方树。下文除特殊强调外,所有图皆为无向图。引入割点:在图中,删除某个点后,导致图不再连通的点。点双连通:在一张图中,取两个点\(u\)、\(v\),无论删去哪个点(除\(u\)、\(v\)自身外),\(u\)、\(v\)都能连通,我们就说\(u\)和\(v\)点双连通。点双连通分量(后文称点双):对于一个无向......
  • 圆方树学习笔记
    前置芝士边双连通与点双连通oi-wiki上是这样说的:在一张连通的无向图中,对于两个点\(u\)和\(v\),如果无论删去哪条边(只能删去一条)都不能使它们不连通,我们就说\(u\)和\(v\)边双连通。在这里我们需要得出一个非常重要的性质:边双连通具有传递性。通俗来说,就是当\([x,y]\)......
  • 圆方树
    小粉兔圆方树兔已经讲的非常好了,我就讲我的理解吧!!!大多数情况下,图论是比树结构要复杂多的,所以引入了一个圆方树的一种数据结构。把无向图转化为由原点与点双连通分量组成的树,原图的每一个点都是一个圆点,每一个点双都是一个方点,所以形成的新图有\(n+c\)个点,每个点双转为方点时......
  • 圆方树
    点双联通分量:对一张图,若其不含割点,则其为一个点双。1,对于点双中的两个点(除只有两点一边的特殊图),可以视作其必然存在两条不同的简单路径,使两者经过的并集为空。2,对于点双中任意一对点,经过它们的简单路径的并集一定为点双本身,意即可以认为两点间简单路径可以通过点双内任意一点。......
  • 圆方树
    定义割点:无向图中,若删除点及其连边,连通块变多,那么被删除的点为割点点双连通:若无向图中点对\(x,y\),删除任意非\(x\)和非\(y\)节点后,\(x\)和\(y\)任然连通,陈\(x,y\)点双连通点双连通子图:无向图中的一个子图\(G\),\(G\)中任意2点都是联通的,那么称\(G\)为原图的点双......
  • 圆方树学习笔记 & 最短路 题解
    前言圆方树学习笔记,从一道例题讲起。题目链接:Hydro&bzoj。题意简述仙人掌上求两点距离。题目分析为了把仙人掌的性质发挥出来,考虑将其变成一棵树。圆方树就是这样转换的工具。先讲讲圆方树的概念:原图上的点为圆点,每个点双对应一个方点,树边都是方点连向点双内的圆点。具......
  • 圆方树
    定义圆方树:将无向图转化为树形结构的数据结构,使得树上2点路径上的点都是原图的必经点。圆点:原无向图\(G\)中的点,仍然保留在圆方树中,称之为圆点。方点:将每一个点双连通分量新建一个“方点”。树边:每一个方点都向对应的点双内的圆点连边。基本性质:性质一:圆方树的总点数=......
  • 圆方树
    一些概念割点:无向图中,若删除点x及其连边,连通块变多,那么x为割点。点双连通:若点对x和y,删除任意非x和非y节点后,x和y仍然联通,称x和y点双连通。点双联通子图:无向图中的一个子图G,G中任意两点都是点双连通的,那么G为原图的一个点双连通子图。点双联通分量:无向图中的极大点双联通子图......