Graph & Tree
2024-10-08 18:39:59
图论学习笔记
TYQ图论真是个渣渣呢
所以TYQ决定猛补图论
好的从0x60开始
表示博客园不用Latex真的烦呢QAQ,公式难打的要命QAQ
0x60~0x62
最短路讲解跳过
最小生成树:
- Kruskal:
挺容易的,贪心的选最大值就好了
时间复杂度emmmO(mlogm),适用于稀疏图
- Prim
首先只在最小生成树中加入root节点
设两个集合S(剩余点),T(生成树)
每次找到两个点,使得他们的连线最短
时间复杂度O(n2),多用于稠密图
0x63~0x64
众所周知树是一种特殊的图,所以我们这里采用链式前向星存边
树的直径:
- 树形Dp:
- demo:
void dp(int x){
v[x] = true ;
for(int i=head[x]; i;i = Next[i]){
int y = ver[i];
if(v[y])continue ;
dp(y);
ans = max(ans,d[x]+d[y]+edge[i]) ;
d[x] = max(d[x],d[y]+edge[i])
}
}
//本代码同算法竞赛进阶指南书中代码- 两次Dfs/Bfs
- 从任意一个节点出发找到离他最远的点p
- 从p出发找到离他最远的点q
- 那么p到q为树的一条直径
- demo
void dfs0(int step,int x){
d[x] = step ;
v[x] = true ;
for(int i=head[x]; i;i = Next[i]){
if(!v[i])
dfs0(step+,i) ;
}
if(maxd<step){
maxd = step;
p = x ;
}
}
void dfs1(int step,int x){
d[x] = step ;
v[x] = true ;
for(int i=head[x]; i;i = Next[i]){
if(!v[i])
dfs1(step+,i) ;
}
if(maxd<step){
maxxd = step;
q = x ;
}
}
LCA
找出x与y的最近公共祖先
- 暴力
- 从x节点向上跳,标记所有跳过的节点
- 再从y向上跳,遇到已标记的节点则停止
- 期望时间复杂度O(logN),实际上珂以卡成O(N)
- 树上倍增法
- 设F[x,k]表示x的2k辈祖先,若不存在则为0
- 我们执行一次广/深度优先遍历以求出F数组
- 然后就可以O(logN)回答询问了
- tarjan算法
- 本质上是优化倍增法
- 离线算法,需要一次性读入全部询问
- 在tarjan算法执行的任意时刻,树上的节点分为三类:
- 已经访问完毕并且回溯的节点,标记值为2
- 已经开始递归,但尚未回溯的节点,标记值为1
- 其他节点,标记值为0
- 对于正在访问的节点x,他到根节点的路径已经标记为1
- 若y是已访问完的节点,则LCA(x,y)就是从y走到根节点的路程中第一个标记为1的节点
- 优化:当一个节点获得2的标记的时候,合并它所在的集合与它的父节点所在的集合
- 那么每次查询就可以直接使用getfa(y)了
- 时间复杂度为O(N+M),不会证
- ST表:
- dfs一遍,得到特殊的长度为 2*n-1 dfs序,然后维护一个在dfs序上的区间深度最小值,而拥有这个最小深度值的节点就是我们要求的LCA。
- 使用ST表预处理珂以O(1)回答询问
- 时间复杂度O(NlogN),且是在线算法
- 树链剖分:
树剖求LCA的速度还很快,O(N)预处理,O(logN)查询,相较于倍增LCA更快,而且求LCA那部分更好写,但是dfs部分比较难写.
树剖求LCA可能相较于倍增最大的优势是空间复杂度较低,只要O(N)
整个算法流程就是先树剖O(N)然后一个判断u与v是否在同一条重链,不在就往上跳,最后得到LCA,在就可直接得到LCA
- 至于为什么查询是O(logN)的,因为重链只有 logN 条,所以是O(logN)的
- 就是常数大点QAQ
树上差分
- 例题
- 我们定义一条附加边(x,y)覆盖的边为主要边构成的树中,x,y之间路径上的边
- 那么若第一步切断覆盖了0次的主要边,则可任意斩断一条附加边
- 若第一步切断覆盖了1次的主要边,则第二部方法唯一
- 若斩断覆盖了两次及两次以上的主要边则无解
- 那么问题就转化为给定一个无向图和一颗生成树,求每条主要边被附加边覆盖的次数
- 那么我们把一条附加边(x,y)覆盖改为把数上x,y两个节点点权加一,LCA(x,y)点权减一
- 最后进行遍历,求出F[x]代表以x为根的子树的节点点权之和
- 那么F[x]就是x与其父亲之间连边被覆盖的次数
基环树
- 树加上一条边
- 构成的环叫做基环
- 跟树差不多,但要先dfs找环,先考虑子树,再考虑环
- 可能以后会替代树?毕竟都在考仙人掌了
- JZOJ考过
接下来我要换Markdown了QAQ
引用:算法竞赛进阶指南
Warning!
本文由 TYQ 创作,采用 知识共享署名 4.0 国际许可协议进行许可。
转载要与作者联系,并需在正文明显处署名作者且注明文章出处。
对了,我永远喜欢C++啊。
最新文章
- 认识ASP.NET 5项目结构和项目文件xproj
- JavaScript异步编程的主要解决方案—对不起,我和你不在同一个频率上
- EcmaScript相关文档
- R语言-Kindle特价书爬榜示例 &; 输出HTML小技巧
- 使用MVVM框架(avalonJS)进行快速开发
- Redis 数据持久化(一)
- WEB-INF下jsp跳转
- EmberJS路由详解
- [codeforces 241]A. Old Peykan
- jq三级全选全不选
- 数据分析≠Hadoop+NoSQL,不妨先看完善现有技术的10条捷径(分享)
- asp实现关键词不区分大小写搜索并高亮显示
- Java基础学习笔记2-循环
- 浅谈android的am命令
- ubuntu 安装 google Gtest [转]有效性待验证
- 【Arduino】Arduino接收字符串
- 《深入理解Java虚拟机》(四)虚拟机性能监控与故障处理工具
- python3的C3算法
- 远程桌面web连接
- git协议
热门文章
- 环境变量和文件查找&;文件打包与解压缩
- mybatis今年笔记
- Java中的Math.abs()
- 【pwnable.kr】col
- HttpServlet中文乱码问题
- Element.scrollIntoView() 和 document.elementFromPoint ()
- VS Code 配置vue开发环境
- C++ Opencv播放AVI
- Tensorflow学习教程------tensorboard网络运行和可视化
- luogu P4219 [BJOI2014]大融合