[L2] 20_图论

核心哲学：图论不是在画点和线，而是在建立一套“状态”与“转换”的规则。

1. 知识图谱与演化

• 核心工具: 最短路建模、约束转化、流量平衡、结构压缩。

• 演化路径:

  1. 遍历：能不能走通？（ DFS / BFS ）

  2. 最短路：寻找代价最小或收益最高的走法。（ Dijkstra / SPFA ）

  3. 流与匹配：资源分配与冲突解决。( MaxFlow/MinCost )

  4. 结构转化：将有环图转化为DAG或树。( SCC/圆方树 )。

2. 决策矩阵

• 代价最小 / 距离最近 / 差分约束：最短路体系。

• 资源分配 / 二选一模型 / 费用控制：[[网络流专题]]。

• 必经点 / 环结构处理：[[连通性专题]] (缩点/圆方树)。

• 最近公共祖先 / 树上路径统计：[[树论专题]] (LCA/点分治)。

• 二分图下的最大配对：[[匹配专题]]。

3. 核心板块索引

3.1 [L3] 21 图论基础

• 存图与遍历：如何存图，如何遍历。

• 拓扑排序：DAG 上的最长路。

• 欧拉回路与路径：一笔画问题。

• 最短路体系： Dijkstra, SPFA, Floyd.

3.2 [L3] 22 树论专题

• LCA 体系：寻找最近公共祖先，倍增/树链剖分。

• 树上差分：树上的前缀和差分。

• 树链剖分：将非线性的树结构转化为线性的数组结构。

• 生成树理论：生成树、MST、Kruskal / Prim / Borůvka 与交换性质。

• 生成树题型整理：瓶颈路、换边、数量限制与隐式完全图建模。

• 直径与重心：树的骨架与平衡点。

• [[Note] 点分治]：树上大规模路径统计。

• [[Note] 虚树]：压缩树上关键点。

• [[Note] 矩阵树定理]：一张图的生成树个数计数问题。

3.3 [L3] 23 连通性专题

• SCC 缩点: 有向图强连通分量。

• [[Note] BCC 双连通]: 割点、桥。

• [[Note] 圆方树]: 仙人掌图与广义圆方树。

• [[Note] 2-SAT]: 布尔可满足性问题。

3.4 [L3] 24 匹配专题

• [[Note] 二分图匹配]: 匈牙利算法。

• [[Note] KM 算法]: 带权二分图最佳匹配。

3.5 [L3] 25 网络流专题

• [[Note] 最大流]: Dinic 算法。

• [[Note] 费用流]: MCMF.

• [[Note] 最小割建模]: 最大权闭合子图等模型。

• [[Note] 上下界网络流]: 流量守恒的扩展。

• P1231 教辅的组成：用拆点边限制中间对象的总使用次数；

• P2057 善意的投票 与 P2762 太空飞行计划问题：分别用割表达二元局部代价与带强制依赖的最大权闭合；

• P1251 餐巾计划问题：在时间轴上区分使用前后的资源状态，再用费用流选择购买或洗涤；

• P4015 运输问题：把单位匹配推广为多单位供给、需求与运输费用。

4. 近期推荐

• P1251 餐巾计划问题：先把同一天的干净需求与使用后脏资源拆成两种状态，再连接跨天洗涤转移；
• P2057 善意的投票：让割的两侧表示两种决策，使改变意愿与朋友冲突分别对应局部割代价；
• P2762 太空飞行计划问题：用无限容量边禁止违反依赖的割，得到最大权闭合集合；
• P1231 教辅的组成：三类物品共享一个中间对象时，用节点容量而非三维匹配建模。