常见优化建图技巧

## 线段树优化建图 >有 $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](https://www.luogu.com.cn/problem/CF786B)（板子题，最短路） [P5025 [SNOI2017]炸弹](https://www.luogu.com.cn/problem/P5025)（强连通分量） [P3588 [POI2015]PUS](https://www.luogu.com.cn/problem/P3588)（拓扑排序，需要建虚点） ### 其他数据结构优化建图 使用主席树、树套树、KD-Tree 等其他数据结构，或者分块、cdq 分治等其他技巧，也可以优化建图，需要具体题目具体分析。 习题： [P5471 [NOI2019]弹跳](https://www.luogu.com.cn/problem/P5471)（KDT/树套树优化建图+最短路，但有更优秀的做法） [P5331 [SNOI2019]通信](https://www.luogu.com.cn/problem/P5331)（分治/主席树优化建图+费用流，也可用 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](https://www.luogu.com.cn/problem/P6378)（2-SAT） [CF1215F Radio Stations](https://www.luogu.com.cn/problem/CF1215F)（2-SAT） [CF1007D Ants](https://www.luogu.com.cn/problem/CF1007D)（2-SAT+树剖+线段树上前缀优化建图） [题解](https://www.luogu.com.cn/blog/221955/solution-cf1007d) [P3783 [SDOI2017]天才黑客](https://www.luogu.com.cn/problem/P3783)（字典树+最短路） ## 不直接建边的优化建图 例题：[P5471 [NOI2019] 弹跳](https://www.luogu.com.cn/problem/P5471) 暴力做法：树套树优化建图，需要动态开点，所以点数和边数分别为 $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】逛森林](https://www.luogu.com.cn/problem/P5344)。 这种不直接建边的优化建图方法也可以在最短路以外的问题中使用，比如 [P7712 [Ynoi2077] hlcpq](https://www.luogu.com.cn/problem/P7712) 求割点。 习题： [P5344 【XR-1】逛森林](https://www.luogu.com.cn/problem/P5344) [题解](https://www.luogu.com.cn/blog/221955/solution-p5344) [P4473 [国家集训队]飞飞侠](https://www.luogu.com.cn/problem/P4473) [题解](https://www.luogu.com.cn/blog/221955/solution-p4473) [P7712 [Ynoi2077] hlcpq](https://www.luogu.com.cn/problem/P7712) [题解](https://www.luogu.com.cn/blog/221955/solution-p7712#) ## 其他优化建图技巧 [P6822 [PA2012]Tax](https://www.luogu.com.cn/problem/P6822)（化边为点+差值优化+最短路）