2 图论
2.1 图论问题的思维过程
2.1.1 图论模型的建立
在解决图论问题时，首先要从原问题中抽象出一个图模型。这个过程中，需确定哪些对象可以作为图的元素（点或边），以及如何用图论的概念（如点权、边权、路径、连通块）来表示这些元素。避免被常规思维限制住，尝试用各种图论的意义去表示原问题中的元素。
例如：
- 限制条件建立模型：从题目中的某个限制条件出发，尝试建立模型。不要局限于一种固定的思维方式。
- 处理全局限制：例如在“Maximum Adjacent Pairs”问题中，全局限制可以通过图论方法进行处理。
- 矩形推箱子问题：将箱子的移动转化为空格的移动，建立关于空格移动路径的图（如“Shifting Dominoes”问题）。
- 区间元素和的判定问题：可以将前缀和建立为点，原图中的元素建立为连接前缀和的边（如“Flip and Reverse”问题）。
2.1.2 图结构的分析
不同的图结构有不同的性质，这些性质可以用于简化问题：
- 树形结构：树有很多优美的性质，例如度数与环的分析，可以通过这些性质证明或简化问题（如“Shifting Dominoes”问题）。深度优先搜索（DFS）是分析树的重要方法，可以通过分析树边和非树边得出许多有趣的性质。
- 有向无环图（DAG）：DAG具有很好的性质，即使在一般图中，也可以先考虑在DAG中的处理方法（如“Sergey’s problem”）。
2.1.3 问题转化
图论中经常需要将问题转化为更容易解决的形式：
- 度数与连通性：度数描述单点限制，连通性描述整体限制，这两者之间可以相互转化（如“电报”问题）。
- 贡献拆分：可以将总贡献拆分到点上或边上（如“Keys”问题）。
- 拓扑关系：如果不同的限制具有拓扑关系，根据题目特性可以忽略一些限制（如“Falling sand”问题）。
- 匹配问题：一类东西只贡献一次的问题可以考虑转化为匹配问题（如“Maximum Adjacent Pairs”）。
- 可达性与连通性：可达性问题可以转化为连通性问题，需要注意连通的双向性和等价性（如“Cow and Vacation”问题）。
2.1.4 寻找结论
在寻找问题的最优解时，可以从以下几个角度入手：
- 点权集中：如果点权集中可以获得更多贡献，可以思考答案是否是原图的最大团。
- 从小处着手：例如从叶子节点入手思考结论，有时可以发现复杂问题变简单（如“绯色 IOI（抵达）”）。
- 拓扑覆盖：在拓扑覆盖问题中，可以考虑原序列上的区间性质（如“Falling sand”问题）。
- 双图策略：通过双图策略寻找性质（如“String Transformation 2”问题）。
- 生成树应用：生成树的应用广泛，答案一定在满足某种性质的生成树上（如“模拟赛6-B”问题）。
2.2 常见算法应用
2.2.1 最短路算法
- Dijkstra算法：Dijkstra算法适用于无负权边的图，通过维护最有可能遍历的点，来找到从起点到其他点的最短路径（如“Mike and code of a permutation”问题）。
- 动态加边：解决到达时间最小的限制，本质是利用连通性说明最早到达时间（如“Dirty Arkady’s Kitchen”问题）。
- Floyd-Warshall算法：Floyd-Warshall算法可以保证一些特殊的转移顺序，适用于所有对所有的最短路径问题（如“Intergalaxy Trips”问题）。
- 删点后的最短路：可以考虑有一条边一定会跨过这个点，拼凑出路径来（如“风之轨迹”问题）。
2.2.2 连通性
- 互达问题：通过连通性解决，重点是传递性。有些问题只有特殊点具有连通性（如“Cow and Vacation”问题）。
- 动态维护连通性：利用低效的动态边双连通分量方法，将非树边的影响转化为赋值标记（如“Bear and Chemistry”问题）。
- 无向图路径的最值问题：通过边权排序转化为维护连通性（如“路径查询”问题）。
2.2.3 拓扑排序
- 拓扑排序：提供一种解构图的顺序，注意拓扑排序中天然带有的可达性（如“Pink Floyd”问题）。
- 拓扑序与反图DFS：按照1到n的顺序在反图上进行DFS，最后回溯的顺序就是拓扑序（如“Mike and code of a permutation”问题）。
2.2.4 问题转化为图论算法
- 差分约束与矩阵问题：利用调整法建出差分约束限制，将矩阵问题转化为图论问题（如“矩阵游戏”）。
- 拓扑排序解决博弈问题：在反图上跑拓扑排序解决带平局的博弈问题（如“Shiritori”问题）。
- 差分约束的反向应用：要求不出现负环等价于有差分约束的合法解，将图上的边写成不等式（如“Negative Cycle”问题）。
- 二分图染色问题：优化连边得到同色性质，利用并查集路径压缩时间复杂度（如“港口设施”问题）。
2.3 树问题
2.3.1 问题转化
- 无根树问题定根：例如路径或删叶子问题，定根是一种重要的思维方法（如“Squid Game”问题）。
- 树的重心：通过考虑重心可以去掉一些关于子树大小的最小公式（如“Distance Matching”问题）。
- 树上最远点问题：转化为直径端点问题（如“CF516D”问题）。
- 最长链问题：与直径问题有关，可以通过直径中点或端点为根建树来解决（如“Spiders Evil Plan”问题）。
2.3.2 树上算法
- LCT（链剖分）：用实边代表同色，虚边代表异色，通过修改一个点到根的路径染色，并用数据结构维护颜色（如“Matches Are Not a Child’s Play”问题）。
- 延迟贪心：关键点尽量放置在最浅的位置（如“Squid Game”问题）。
- 虚树大小的快速计算：可以考虑下标为DFS序的线段树来维护（如“语言”问题）。
2.3.3 常见模型
- 连通块问题：可以在连通块的最浅点统计贡献，利用树形DP来规划最浅点（如“Ridiculous Netizens”问题）。
- 还原树的问题：可以分步还原，先还原特殊点结构，再还原整体结构（如“Restoring Map”问题）。
- 边权和贡献最大问题：考虑长链剖分，通过Kruskal重构树，利用DFS序最大点和最小点的LCA（如“Groceries in Meteor Town”问题）。
- 路径问题：通过点分治解决复杂形式的路径问题（如“Network”问题）。
2.4 网络流
2.4.1 量的意义
- 流量代表加减：流量的流入和流出可以表示加减关系，用来解决一些加减的不等式关系（如“Red-Blue Graph”问题）。
- 流量与代价：流量表示解决要求的途径，费用表示途径的代价（如“Chips Challenge”问题）。
- 路径与不合法关系：用路径表达不合法关系，再用最小割获取最优解（如“Starry Night Camping”问题）。
- 覆盖限制：把需要覆盖的点串联起来，用路径表示覆盖关系（如“奇怪的线段树”问题）。
2.4.2 观察性质
- 网络流解决平面图问题：考虑黑白染色转二分图性质（如“过山车”问题）。
- 网络流解决矩阵问题：用行列
建二分图，有时建单层图更好表达限制（如“Asa’s Chess Problem”问题）。
- 完美匹配与Hall定理：如果原问题与Hall定理有关，可以通过这种关系转化为网络流（如“Construction of a tree”问题）。
- 拆分法：网络流一般解决单点对单点限制，对于多点对单点，可以找结论从答案形式入手（如“Rainbow Triples”问题）。
2.4.3 小技巧
- 单点多重意义：考虑拆点，使限制表达得更明晰（如“过山车”问题）。
- 动态网络流：多个图差别不大时，可以把多出来的边退流（如“模拟赛7-C”问题）。
- 手算最小割：使用枚举法和数据结构维护（如“Rainbow Triples”问题）。
- 保留有用的边：减少边数（如“Bridge Club”问题）。
2.4.4 图匹配问题
- 一般图匹配：通过结论转化成二分图匹配（如“模拟赛5-A”问题）。
- 贪心匹配：在特殊情况下贪心地匹配（如“Add to Square”问题）。
- 二分图的独立性：只需考虑某一部的具体情况（如“Bipartite Blanket”问题）。
- 交错路与数量关系：不能走回头路的博弈问题通过交错路数量关系解决（如“游戏”问题）。
- 有向图求环划分：拆成入点和出点跑二分图匹配（如“边”问题）。
2.4.5 常见模型
- 混合图的欧拉回路：思考度数在原问题中对应的含义，套用模型（如“wait”问题）。
- 最大权闭合子图：解决带强制选取关系的选/不选问题（如“魔法商店”问题）。
- 最长反链：转最小链覆盖，用DFS构造（如“Birthday”问题）。
- 上下界网络流：表示一些强制限制（如“Showing Off”问题）。
