当前位置：首页 > news >正文

图论

news 2025/10/5 13:20:26

图论 Graph Theory

图的遍历

A Path in A Dictionary：找出最小字典序简单路径，对于每个点，按照字典序搜索下一个点，如果第一次搜这点却不能到达终点，那下次就没有必要搜索
建图思想
Train Wreck:任意入栈后的栈不能相同，那么模拟，可以构造出一个树来表示所有时刻的栈，那么此时就可以由此构造一个图来表示，方便后续的处理
思维题
B - Triangle Toggle : 注意到一次操作，对顶点的黑边数的影响分别是0，-2，+2，，所以最终一个顶点最大的黑边数与初始黑边数同奇偶

两遍dfs，第一次dfs，任取一个点，找到离开该点距离最大的点，第二次dfs，以该点为起点，找到离该点最远的点，此时两点距离即为树的直径

简单习题：
AcWing 237. 程序自动分析:需要离散化
带权并查集：AcWing 238. 银河英雄传说[NOI2002]:模板题
解决区间问题：
- 小笨的蓄水池：并查集的点也可以是区间
- 并查区间染色模型: 区间每个元素指向后一位，使得遍历达到线性复杂度
  - AcWing 6100. 奶牛选美
  - 疯狂的馒头
启发式合并：
- [NOIP 2013 提高组] 货车运输,将小的并查集合并到大的之中

一般有两种算法：Kruskal算法和Prim算法
次小生成树:题解

增加理解：AcWing 346. 走廊泼水节:加深你对最小生成树边权的理解，两个完全图（节点数分别是a,b）合并成完全图需要a*b个边
超级源点：应对既有点权还有边权，求最小值时，将点权转化为由超级源点（一般为0）指向该点的边权，再求最小生成树
练习题:
1. [USACO08OCT] Watering Hole G
2. CF1245D. Shichikuji and Power Grid
最大生成树：有时候需要构造最大生成树.
连通块的思想：
最小限度生成树：先不连s，划分成连通块求最小生成树，再相连
野餐规划:上一题是恰好k个，这一题是可以[1,k]个

上述两题的实现在于同时记录并查集合并时边的信息，利用冗余信息优化解题

Floyd算法
Floyd算法中使用前k个节点更新最短路的思维：
- 灾后重建
dijkstra算法
- 最短路模板
- 次短路
  次短路基于最短路算法，再更新最短路的同时记录次短路
- 最短路计数：最短路距离更小方案数直接由前一个点转移，最短路距离相同累加方案数
- 建反图：可以将原图建在每个点+n之后
  邮寄员送信
spfa算法: 负环
- [NOIP 2009 提高组] 最优贸易:有环就可能需要用到spfa，双向spfa
  
  此题也启发我们，最短路算法不一定用来求两点之间最短距离，也可以用来求两点之间路径上的最大值或者最小值
- SLF优化算法.道路与航线:板子优化
分层图:这一层到下一个层，为出现的特殊情况，分多少层取决于出现的次数
- 通信线路
- [NOIP 2009 提高组] 最优贸易: 此题亦可用分层图来写，第一层到第二层同一点的边权为水晶球的负值，表示买入，第二层到第三层同一点的边权为水晶球的正值，表示卖出，这样就形象地表示买入卖出，到3*n的点最短路就是赚的钱
- 分层图有时候会出现内存不够的情况
  - 可以考虑建立中转节点来实现层与层的转化，同时也不必使每一层都完整，离散化点的编号
  - 或者只分两层，滚动求最短路，Asia EC Online 2025 (I) M. Teleporter
状压最短路
G. Rudolf and CodeVid-23

连通性:主要考察连通性，割点，割边，缩点

连通性
图在建立时的连通性就在变化：
P2700 逐个击破：该题给定K个点不能连通，逆向思考，如果建图的时候，保证这个k个点始终不连通，那么就达成了目标
连通分量
图的连通分量:难点主要在遍历联通的点上，从二进制角度思考，对于整数x,应该遍历x取反后，所有1的位置组成的二进制子集。题解
缩点
模仿者:简单题