图论 Graph Theory
基础
-
图的遍历
A Path in A Dictionary:找出最小字典序简单路径,对于每个点,按照字典序搜索下一个点,如果第一次搜这点却不能到达终点,那下次就没有必要搜索
-
建图思想
Train Wreck:任意入栈后的栈不能相同,那么模拟,可以构造出一个树来表示所有时刻的栈,那么此时就可以由此构造一个图来表示,方便后续的处理 -
思维题
B - Triangle Toggle : 注意到一次操作,对顶点的黑边数的影响分别是0,-2,+2,,所以最终一个顶点最大的黑边数与初始黑边数同奇偶
树 Tree
-
基础
在树(或二叉树等树形结构)中,节点的 “度”指的是该节点拥有的子节点的数量叶节点,叶节点是度为0的节点:D. Arboris Contractio:最终的图是菊花图,因此找出最小的点使得其直接相连的非叶节点最少
-二叉树- 对于任意二叉树,结点总数n由度为 0(叶子结点)、度为 1、度为 2的结点数之和组成
- 对于任意二叉树,度为 0 的结点数比度为 2 的结点数多 1
-
计数问题
Pair Counting: 理解好题意,题解
树的直径
两遍dfs,第一次dfs,任取一个点,找到离开该点距离最大的点,第二次dfs,以该点为起点,找到离该点最远的点,此时两点距离即为树的直径
并查集
- 简单习题:
AcWing 237. 程序自动分析:需要离散化 - 带权并查集:AcWing 238. 银河英雄传说[NOI2002]:模板题
- 解决区间问题:
- 小笨的蓄水池:并查集的点也可以是区间
- 并查区间染色模型: 区间每个元素指向后一位,使得遍历达到线性复杂度
- AcWing 6100. 奶牛选美
- 疯狂的馒头
- 启发式合并:
- [NOIP 2013 提高组] 货车运输,将小的并查集合并到大的之中
最近公共祖先
倍增法
dfs序
树链剖分
本人只会树链剖分,多写,方便以后写树链剖分
小红的树不动点:不断找满满足第i个点是不动点子树的深度dep,会有个dep个子树满足第i个点是不动点子树
最小生成树
一般有两种算法:Kruskal算法和Prim算法
次小生成树:题解
- 增加理解:AcWing 346. 走廊泼水节:加深你对最小生成树边权的理解,两个完全图(节点数分别是a,b)合并成完全图需要a*b个边
- 超级源点:应对既有点权还有边权,求最小值时,将点权转化为由超级源点(一般为0)指向该点的边权,再求最小生成树
练习题:- [USACO08OCT] Watering Hole G
- CF1245D. Shichikuji and Power Grid
- 最大生成树:有时候需要构造最大生成树.
连通块的思想: - 最小限度生成树:先不连s,划分成连通块求最小生成树,再相连
- 野餐规划:上一题是恰好k个,这一题是可以[1,k]个
上述两题的实现在于同时记录并查集合并时边的信息,利用冗余信息优化解题
图论
拓扑排序
-
基础
C. Max Tree:因为是树,所以无环,题目的条件仅仅让你决定边的方向,于是形成拓扑图,以此来决定答案 -
与状态压缩结合
可达性统计
最短路
-
Floyd算法
Floyd算法中使用前k个节点更新最短路的思维:- 灾后重建
-
dijkstra算法
- 最短路模板
- 次短路
次短路基于最短路算法,再更新最短路的同时记录次短路 - 最短路计数:最短路距离更小方案数直接由前一个点转移,最短路距离相同累加方案数
- 建反图:可以将原图建在每个点+n之后
邮寄员送信
-
spfa算法: 负环
- [NOIP 2009 提高组] 最优贸易:有环就可能需要用到spfa,双向spfa
此题也启发我们,最短路算法不一定用来求两点之间最短距离,也可以用来求两点之间路径上的最大值或者最小值
- SLF优化算法.道路与航线:板子优化
- [NOIP 2009 提高组] 最优贸易:有环就可能需要用到spfa,双向spfa
-
分层图:这一层到下一个层,为出现的特殊情况,分多少层取决于出现的次数
- 通信线路
- [NOIP 2009 提高组] 最优贸易: 此题亦可用分层图来写,第一层到第二层同一点的边权为水晶球的负值,表示买入,第二层到第三层同一点的边权为水晶球的正值,表示卖出,这样就形象地表示买入卖出,到3*n的点最短路就是赚的钱
- 分层图有时候会出现内存不够的情况
- 可以考虑建立中转节点来实现层与层的转化,同时也不必使每一层都完整,离散化点的编号
- 或者只分两层,滚动求最短路,Asia EC Online 2025 (I) M. Teleporter
-
状压最短路
G. Rudolf and CodeVid-23
图论的连通性
- 传递闭包:模板题,改改floyd就好,可以用bitset优化
AcWing 343. 排序
连通性:主要考察连通性,割点,割边,缩点
- 连通性
图在建立时的连通性就在变化:
P2700 逐个击破:该题给定K个点不能连通,逆向思考,如果建图的时候,保证这个k个点始终不连通,那么就达成了目标
连通分量
图的连通分量:难点主要在遍历联通的点上,从二进制角度思考,对于整数x,应该遍历x取反后,所有1的位置组成的二进制子集。题解 - 缩点
模仿者:简单题