7.28

  • 虚拟源点，可以用来处理一些既有点权又有边权的图论问题

例题：CF938D

题意就是让你去买票，每个城市都有不同价格的票，城市之间有道路，道路有过路费，问你以每个城市为起点，买一张票最少要花多少钱。

$1e5$​ 范围。

我们发现这题显然是最短路，但是有边权的情况下，每个点也有不同的权值，这就导致我们很难做。此时可以考虑建立虚拟源点。

我们运用假设性原则，假设有一个点，它连向了每一个城市，然后连接的边权为当前城市的票价，然后以这个点为源点跑一边最短路就彳亍了。

正确性可以自己手玩一下qwq。

8.4

  • 并查集连续合并的优化，思想是类似于 KMP 的数组+跳跃式合并

例题：CF566D

题目主要就是问你并查集怎么把 $x-y$ 的所有元素合并起来。

暴力，$5e5$ 过不得，然后这里要用一个类似于 KMP $next$ 数组的优化。

我们可以搞一个 $next$ 数组，用来存第 $i$ 个点之后，第一个和它不处于一个集合内的元素，然后动态更新 $next$ ，同时每次 $i=nt[i]$。

具体实现可以看代码，洛谷交了。