• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

基环树乱写

开发技术 开发技术 4小时前 3次浏览

如果你像本节的标题一样,恭喜你成功学会了这个东西洗洗睡吧
珍爱生命,建议远离

基本

基环树是一种图结构,直观表现为树套环
狭义的基环树指树上两个点之间多一条边,整个图中有且仅有一个环
广义上指边数和点数相同的图,即一个基环树森林
特别的,对于有向图,每个点有且仅一条出边的为内向树,有且仅有一条入边的为外向树
对于内向边,由于从任意一点都可以走到环上,所以可以找环
对于外向边,如果把环视为根,适合进行从根dfs,一般树算法大多可以适用
个人习惯建双向边,标记一下每条边的种类方便操作

操作

首先核心操作找环,个人用dfs,也有大佬直接循环的

void dfs(int x,int f)
{
	v[x]=1;
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==f)continue;
		if(v[y])
		{
			c.push_back(y);
			while(x!=y)
			{
				c.push_back(x);
				x=fa[x];
			}
			flag=1;return;	
		}
		fa[y]=x;dfs(y,x);
		if(flag)return;
	}
}

建内向边或无向边,记录前驱,发现重复就回溯存环,找到之后快速跳出
其他有些是dp,还有些dfs,视题目而定

NOIP2018 旅行

这个可以(n^2)水过,然而我写的是(nlog n)
树的分随便做,把儿子排序就行,关键在于基环树部分
发现在走环时候可能存在一次回溯,要快速找到这个回溯点
对于环上的点(u)和他环上下一个点(v),如果不从(u)走到(v)而是回溯,那么需要满足:
(v)(u)最大的儿子,并且回溯时经过的第一个节点小于(v)
如果(v)不是最大儿子,它后面一定还有,这些回溯后无法便利到
因为只有回溯后更优才要回溯,那么要保证回溯到的第一个未走过节点小于(v)
先找环,然后模拟一遍环上的过程,动态维护回溯到的第一个节点(不一定是环对面的点),确定回溯地之后断边

ICPC2019 Hobson 的火车

分两部分:树部分和环部分,对于一个点考虑它对多少点有贡献
从每个环上的点开始往下dfs,用栈维护它的(k)级祖先可以做到(O(n))
先考虑树上的贡献,一个点对上面一条祖先链有贡献,可以差分
枚举每个点看它对环上的贡献,同样是连续一段,也可以差分
注意环上的点不要被重复覆盖,贡献长度最好和环长-1取min

创世纪

基环树dp,套路是断边做两边有限制的树形dp
选择环上两点断开,取(p)为根做一遍取(max(f_{p,0},f_{p,1})),再强制(p)管辖(a[p])做一遍取(f_{p,0}),max就是答案

Rendezvous

基环树LCA,类比普通LCA,分类讨论即可
如果不在一个联通块显然无解,如果在一颗树里直接套路LCA
否则先跳到环上,选择短的一条路走即可

同桌的你

大毒瘤
我把重边直接删了,所以可能同时存在树和基环树
分别dp,相当于边独立集,我把喜好权值设为(10^6),男女权值设为(1),这样就能直接做
还有记录方案,多开数组+记录路径,除了极其复杂之外没有别的难点
最后让付哥哥手写了个哈希表才卡过

总结

总的来说基本考验代码能力,细节比较多,通常需要调比较久
建议每写一个dfs之后都运行一遍,你永远不知道接下来发生什么


程序员灯塔
转载请注明原文链接:基环树乱写
喜欢 (0)