首页 > 其他分享 >基环树学习笔记

基环树学习笔记

时间:2024-02-23 12:44:43浏览次数:34  
标签:连通 求解 笔记 学习 基环树 条边 2.2 dp

1.定义

基环树,又称环套树,n个点n条边,也就是一棵树多一条边,形成唯一的环,这是保证这n个点n条边构成的是一个连通图的时候才是唯一环,如果图不连通但是每个连通块点数都等于边数的时候这个图就是一个基环树森林,可以有多个环

如果一张有向弱连通图每个点的入度都为1,则称它是一棵 基环外向树。

如果一张有向弱连通图每个点的出度都为1,则称它是一棵 基环内向树

2.常见解题套路

2.1.

将环提出来,此时图就变成了一个环的节点上挂着一些子树,然后将子树的信息合并到环的节点上,再解决环上的问题即可

2.2.

忽略环的一条边,当成树来求解,最后加上忽略的边

3.例题

3.1.[ZJOI2008]骑士

本题类似于没有上司的舞会,dp[i][0/1]表示选/不选第i个人的最大值,所以:

\[\begin{cases} dp_{u,1}=\sum_{(u,v)∈E}dp_{v,0} \\ dp_{u,0}=\sum_{(u,v)∈E}max(dp_{v,0},dp_{v,1}) \end{cases} \]

因为有n个骑士,n条关系,所以按关系连边后会形成一个基环树森林,不能直接树形dp,采取方法2.2,先找环,再求解

3.2.「NOIP2018」旅行

采用方法类似于2.2,对于m=n-1,直接DFS,对于m=n,分别枚举这m条边,将其删去,再DFS找最小即可

3.3.[Ioi2008] Island 岛屿

采用方法类似2.1,先求每棵子树的直径,在断环为链用单调队列求解

标签:连通,求解,笔记,学习,基环树,条边,2.2,dp
From: https://www.cnblogs.com/wangsiqi2010916/p/18029253

相关文章

  • 《程序是怎样跑起来的》第五章读书笔记
    从都具有存储程序命令和数据这点来看,内存和磁盘的功能是相同的。在计算机的五大部位中,内存和磁盘也都也都被归类为存储部件。不过利用电流来实现存储的内存,同利用磁效应来实现存储的磁盘,还是有差异的,而从存储容量来看,内存是告诉高价,而磁盘则是低速廉价。程序保护在存储设备中,通过......
  • 扫描线学习笔记
    1.引入扫描线多用于图形上,是一条线在图形上扫来扫去,它一般被用来解决图形面积,周长,以及二维数点等问题。2.扫描线求面积并如下图:我们模拟一条扫描线,使它从下往上扫过整个平面,这条扫描线会在遇到横向线段的时候停下来更新一些东西。那么整个图形就可以找出四条线段,如图:更新的......
  • 【文化课学习笔记】【数学】函数(上)
    【数学】函数(上)概念【本质】唯一确定的对应。【定义】一般地,设\(A,B\)是非空的实数集,如果对于集合\(A\)中的任意一个数\(x\),按照某种确定的对应关系\(f\),在集合\(B\)中都有唯一确定的数\(y\)和它对应,那么就称\(f:A\toB\)为从集合\(A\)到集合\(B\)的一个函数......
  • SpringMVC学习
    SpringMVC是Spring提供的用于简化web开发的框架。 1.5 Servlet能够响应请求的对象。接收请求,返回响应SpringMVC可以认为是Servlet的封装。  1.6SpringMVC开发流程回顾各种配置。Controller,DispatchServlet, 1.7......
  • 《程序是怎样跑起来的》第四章读书笔记
    内存IC中内存IC中有电源,地址信号,数据信号,控制信号等用于输入输出的大量引脚,通过为其指定地址,来进行数据的读写。像WR和RD这样可以让IC运行的信号称为控制信号。当WR和RD同时为0时,写入和读出的操作都无法进行。编程语言中的数据类型表示存储的是何种类型的数据。指针也是一种变量,......
  • 笛卡尔树学习笔记
    1.定义笛卡尔树是一种特殊的二叉树,同时满足小根堆和二叉搜索树的性质,笛卡尔树的每个节点有两个值(k,w),k满足二叉搜索树性质,w满足小根堆性质。Treap也是一种笛卡尔树2.性质如果k,w是分别两两不同的,那么笛卡尔树也是唯一的对于一颗笛卡尔树,它的中序遍历是原序列a在原序列中......
  • Syscall笔记
    本文首发:https://xz.aliyun.com/t/13687基础知识我们知道,系统核心态指的是R0,用户态指的是R3,系统代码在核心态下运行,用户代码在用户态下运行。系统中一共有四个权限级别,R1和R2运行设备驱动,R0到R3权限依次降低,R0和R3的权限分别为最高和最低。而我们的**syscall**是一个计算机......
  • rabbitmq交换机类型学习
    1Exchanges概念​RabbitMQ消息传递模型的核心思想是:生产者生产的消息从不会直接发送到队列。实际上,通常生产者甚至都不知道这些消息传递传递到了哪些队列中。​相反,生产者只能将消息发送到交换机(exchange),交换机工作的内容非常简单,一方面它接收来自生产者的消息,另一方面......
  • rabbitmq学习记录
    一、RabbitMQ的概念RabbitMQ是一个消息中间件:它接受并转发消息。你可以把它当做一个快递站点,当你要发送一个包裹时,你把你的包裹放到快递站,快递员最终会把你的快递送到收件人那里,按照这种逻辑RabbitMQ是一个快递站,一个快递员帮你传递快件。RabbitMQ与快递站的主要区别在于:它不......
  • 学习环境(浏览器与编辑器)配置,HTTP常识
    学习大纲一前端html5/css3写页面2.JaveScript/ES6/jQuery/Bootstrap写页面逻辑二PHP编程PHP语法,数据类型,面向对象,命令空间,数据库POD,Composer,MVC三Laravel框架微信小程序,CRM,Laravel基础,项目分析,数据表创建,前后台的完整开发流程,项目优化与项目上线学习......