常见优化建图技巧

· · 个人记录

线段树优化建图

有 n 个点，m 个连边操作，操作有三种：

1 x l r a 从 x 向区间 [l,r] 的点连长度为 a 的边。

2 x l r a 从区间 [l,r] 的点向 x 连长度为 a 的边。

3 x y l r a 从区间 [x,y] 的点向区间 [l,r] 的点连长度为 a 的边。

最后求出 1 到 n 的最短路。

n,m\leq 10^5

直接连边边数是 O(n^2m) 级别，需要优化。

对于区间问题，通常用线段树优化。

建两棵线段树，分别为“正线段树”和“反线段树”，正线段树上父亲向儿子连长度为 0 的边，反线段树上儿子向父亲连长度为 0 的边。

对于 1 操作，找到区间 [l,r] 对应的正线段树上的点，从 x 向这些点连长度为 a 的边。

对于 2 操作，找到区间 [l,r] 对应的反线段树上的点，从这些点向 x 连长度为 a 的边。

对于 3 操作，新建一个虚点，从 [x,y] 对应的反线段树上的点向虚点连长度为 0 的边，从虚点向 [l,r] 对应的正线段树上的点连长度为 a 的边。

最终点数为 O(n+m) 级别，边数为 O(m\log n) 级别，算上最短路的复杂度，总时间复杂度为 O(m\log^2 n) （二叉堆优化 dij），或者 O((n+m)\log n) （斐波那契堆优化）。

习题：

CF786B Legacy（板子题，最短路）

P5025 [SNOI2017]炸弹（强连通分量）

P3588 [POI2015]PUS（拓扑排序，需要建虚点）

其他数据结构优化建图

使用主席树、树套树、KD-Tree 等其他数据结构，或者分块、cdq 分治等其他技巧，也可以优化建图，需要具体题目具体分析。

习题：

P5471 [NOI2019]弹跳（KDT/树套树优化建图+最短路，但有更优秀的做法）

P5331 [SNOI2019]通信（分治/主席树优化建图+费用流，也可用 KM 算法解决）

前缀优化建图

有 n 个点，m 个连边操作，操作有三种：

1 x l r a 从 x 向区间 [l,r] 以外的点连长度为 a 的边。

2 x l r a 从区间 [l,r] 以外的点向 x 连长度为 a 的边。

3 x y l r a 从区间 [x,y] 以外的点向区间 [l,r] 以外的点连长度为 a 的边。

最后求出 1 到 n 的最短路。

n,m\leq 5\times10^5

线段树优化建图显然可做，但是有更好的方法。

注意到“区间 [l,r] 以外”等价于前缀 [1,l-1] 并上后缀 [r+1,n]。

新建 n 个点，pre_i 对应前缀 [1,i]。从 pre_i 向 i 和 pre_{i-1} 分别连长度为 0 的边。再新建 n 个点，suf_i 对应后缀 [i,n]，连边同理。

对于操作 1，从 x 向 pre_{l-1} 和 suf_{r+1} 连长度为 a 的边。后两种操作同理。

最终点数为 O(n) 级别，边数为 O(n+m) 级别。

习题：

P6378 [PA2010]Riddle（2-SAT）

CF1215F Radio Stations（2-SAT）

CF1007D Ants（2-SAT+树剖+线段树上前缀优化建图） 题解

P3783 [SDOI2017]天才黑客（字典树+最短路）

不直接建边的优化建图

例题：P5471 [NOI2019] 弹跳

暴力做法：树套树优化建图，需要动态开点，所以点数和边数分别为 O(n\log^2n) 和 O(m\log^2n) 级别，总复杂度 O(m\log^3n)，不能通过。

优化做法：

一般的 dij 堆中存的是点，这里堆中存边（即题目中的弹跳装置）。

设 w_i 为边 i 的权值，d_x 为 点 x 的最短路。若 x 为边 i 的起点，设 g_i=d_x+w_i。

堆中的边按 g 从小到大排序，于是每次取出的边的 g 值和访问到点的最短路都是单调递增的，每个点第一次被访问到即为最短路，之后可以直接删掉这个点，每条边用过也可以删掉（此题中边只有一个起点所以不需要删边，但是习题需要）。

于是每个点和边都只需要访问一次，这部分复杂度为 O(m\log n)。

此题中复杂度瓶颈在于查询每条边能到达的还没被访问过的点，用树套 set 维护，O(m\log^2n)。

区间向点/区间连边也可以做，见 P5344 【XR-1】逛森林。

这种不直接建边的优化建图方法也可以在最短路以外的问题中使用，比如 P7712 [Ynoi2077] hlcpq 求割点。

习题：

P5344 【XR-1】逛森林 题解

P4473 [国家集训队]飞飞侠 题解

P7712 [Ynoi2077] hlcpq 题解

其他优化建图技巧

P6822 [PA2012]Tax（化边为点+差值优化+最短路）