优化建图是一种图论中的辅助方法，通过建辅助点的方法将图优化，通常，这可以大幅度减少算法的时间复杂度和空间复杂度。 例题 檀香梅 题解 这道题如果使用传统的直接建图，则一共有 $O(n^2)$条边，在 TLE 之前就已经 MLE 了，所以我们考虑到使用其他方法。 考虑到这道题...

2834 字 丨 9.4分钟

考虑下面的这个问题： www.luogu.com.cn 显然，这是一道最短路，但是直接建图肯定会 $TLE$，相当于你要把 $l$ 到 $r$ 之内的点全部连一条边，这样单次操作的事件复杂度是 $O(n)$ 的，所以，我们需要考虑一种聪明的方式来优化它。 考虑到这是一堆区间...

3819 字 丨 12.7分钟

问题引入 假如我们要用一个有向无环图存一个字符串的所有子串，然后跑各种图论中的算法，以 $abaab$ 为例，该怎么做 SAM介绍 注意到，这种方法的时间在最劣的情况下是 $O(n^2)$ 的，因为其中还有很多部分可以优化 观察到 $a→a→b...

8978 字 丨 29.9分钟