图论学习现阶段自行总结

发表于 分类于

断断续续学图论也有一段时间了，感觉喜忧参半吧。趁这次集训做总结的机会，把脑子里零零散散的东西理一理，也算是对自己这一阶段的状态做一个交代。

现阶段图论学习进度总结

详见 提高组图论复习清单.pdf，该文档中有对目前的图论知识做详细总结。下面分类给出概述。

1. 基础搜索与遍历

  • DFS：找连通块、判环、记录DFS序、Tarjan类算法、树形DP
  • BFS：无权图最短路、多源BFS、网格图处理
  • 0-1 BFS：边权只有 $0$ 和 $1$ 时的线性优化（双端队列）

2. 最短路算法

  • Dijkstra：边权非负的最短路（优先队列）
  • Bellman-Ford / SPFA：处理负权边、判负环
  • Floyd：小规模全源最短路、传递闭包
  • 分层图最短路：处理”最多使用 $K$ 次特殊操作”问题，即建 $K$ 层图

3. 连通性与缩点

  • 并查集：动态加边、离线删边、辅助最小生成树
  • 强连通分量（Tarjan/Kosaraju）：有向图互相可达、缩点后变DAG
  • 割点与桥：无向图的连接
  • 功能图：每个点出度为 $1$ 的特殊结构（环+树）

4. 关于DAG

  • Kahn算法：拓扑排序、判环
  • DAG上DP：方案数、最长路、最短路、博弈状态

5. 最小生成树

  • Kruskal：按边权排序+并查集，解决”连通所有点的最小代价”问题
  • 最小瓶颈性质：最大边权最小的生成树

6. 树上技巧

  • DFS序：子树转区间问题
  • LCA（倍增）：树上路径、祖先查询
  • 树的直径：两次DFS/BFS求最长路径
  • 换根DP：每个点作为根时的答案快速计算

7. 二分图

  • 染色判定：是否存在奇环
  • 匈牙利算法：最大匹配、增广路思想
  • Kőnig定理：最小点覆盖=最大匹配（仅二分图成立）

8. 高级技巧

  • 状态图建模：点=位置/资源/状态
  • 反图技巧：从终点反向BFS/最短路
  • 补图BFS：用set维护未访问点，避免显式建补图
  • 欧拉路径：边恰好经过一次的判定
  • 二分答案+图判定：单调性验证

题目练习情况总结

以下为近一年（两学期）的图论练习清单：

主题/平台 NKOJ VJudge
图论基础 \ Graph_First_Lesson
树 树形结构基础 BTreeEx
差分约束 差分约束系统 \
树形DP 树形dp入门 树形DP补充
SCC 图的连通性 夏季专题训练三
二分图 二分图练习 夏季专题训练三
综合练习&补充 \ 夏季专题训练三

通过对表中所有练习的完成情况进行复盘，我发现几个主要问题：

  1. 做题速度太慢。几十道题目中我很少拿到首A，大概就是开始看题时别人已经快想出来了、开始写代码时别人早就过了。这导致我思考时就多半已经有人过了这道题，如果这道题又碰巧特别难，自己就总是想向同学求助——这般被动的学习无疑是对自己的思维成长无益的。
  2. 容错率太低。两个OJ都可以看到总耗时/罚时，数据清楚地暴露了我这方面的缺陷。其中VJudge还可以显示被罚时的次数，我那栏时有一个-5、-8甚至-10，也就是说同一道题我有时需要提交将近十次才能通过，CF/ICPC赛制都算仁慈了，乐多对我来说肯定是最不友好的。这说明我做题时的审题以及（也尤其是）实现时调试的能力都有些欠佳。

但同时，在对比近期作业表现（如 夏季专题训练三）和早期练习表现（如 BTreeEx）后，我也发现了一些进步：

  1. 整体的平均完成度相较于之前有提高。九次作业有七次作业最后完成了所有题目，多做一道题就会收获更多经验。

总体来看，当前的主要问题不在于忘了某个算法的代码，而在于读题后无法快速锁定正确的模型，导致前期思考效率偏低。至于罚时偏高这件事，本质上是调试习惯不好。自我统计一下就会发现，对于一道提高+以上的题目，我平均花在调题上的时间会是写题时间的两倍甚至以上。横向对比一下班上的同学，朋友冯克一调题时就经常以一种我看不懂的诡异方式在代码上到处乱改，两分钟就能把原代码改得面目全非——但是从效果上看，他调题的效率就高得惊人，我实在是惭愧不堪啊。速度方面，短期内可能不会有质的提升，但可以尝试定时训练的方式。读题后五分钟内必须给出一个初步的算法方向，哪怕不确定也比空耗时间要好。

做题技巧总结

上文的PDF原文中已经写得非常详细了，我在这里只补充几条自己觉得确实有用的心得。

  1. 拿到题先问三个问题。 点是什么？边是什么？边有没有方向和权值？如果点没法直接对应到题目里的对象，说明大概率需要建状态图；如果边权有0有1，优先想0-1BFS而不是Dijkstra；如果题目里出现了“互相到达”“互相影响”这类描述，往强连通分量上靠。

  2. 反图是个好东西。 当题目问“所有点中哪些能到达目标点”时，直接对每个点做搜索是笨办法。建反图，从目标点出发跑一次，效率高得多。

  3. 分层图的本质是扩展状态。 不要把它想得太高级，其实就是把当前用了掉的机会数塞进点的编号里，剩下的就是普通最短路。关键点在于估计好总点数和总边数，不要开小了。

  4. 树上路径用LCA，子树问题用DFS序。 一旦判断出原题是树上的问题，优先想这两个工具能不能套上。如果题目要求每个点作为根时的答案，那就是换根DP，第一遍算子树贡献，第二遍做换根转移，套路比较固定。

  5. 关于虚拟源点。 多个起点时建一个虚拟源点连边，代码更干净。虚拟汇点同理，这种小技巧能降低思维的负担。

  6. 关于反向建模。 反图除了用在最短路和BFS上，还有一个用处是处理删除操作。

  7. 关于缩点后的DAG处理。 首先，新图的边需要去重，否则拓扑排序时入度会被重复计算，导致DP顺序错乱。去重的常见做法是用set或者排序后unique，图省事就用 unordered_map<pair<int,int>>，虽然多一个log但数据规模通常能接受。其次，缩点后每个分量的权值合并要慎重，如果原题是点权和，那就把分量内所有点权加起来；如果是问是否存在特殊点，那就用或运算；如果是问路径条数，环内可能无穷多条，那缩点后就不能直接转移了，需要另想办法。

  8. 关于二分图匹配的调试。 匈牙利算法本身很短，但出错的概率一点也不低。最常见的问题是 vis 数组的标记方式。如果用时间戳（即把 vis 改成int，每次dfs传入一个tag）可以免去每次清空O(n)的开销，但要注意tag不能用 $0$，因为 match初始为 $0$。

  9. SPFA毒瘤吗。 SPFA的确最好想也好写，但是它被卡的情况太常见了。我的感受是除非有负权边且数据范围很小，否则尽量别用SPFA。如果负权边数量不多，可以考虑把图转成DAG后用拓扑DP，或者用Bellman-Ford。差分约束题负环的存在本身就是需要判定的，这时候只能用SPFA，但要清楚它的复杂度在最坏情况下是O(nm)。

总结

接下来的集训里，重点会放在两件事上：一是提高建模的敏感度，尽量做到读完题就能判断出该往哪个方向想；二是降低提交次数，把该踩的坑在本地踩完，而不是在OJ上反复试错，因为正规比赛采用的OI赛制没有任何试错机会。至于速度，能提就提吧，提不了至少保证想清楚之后再动键盘，避免做到一半发现思路错了就全部推倒重来。