SDOI2017 R2 天才黑客

最短路好题,快来练习最短路模板吧

传送门

题面

题意

给出一张图,边上有两个参数,一个表示距离,另一个表示口令。定义一次走的路径长度为这条边的距离加上你当前的口令和这条边上的口令的LCP长度,走过一条边以后你的口令就会变成这个边上的口令,最开始口令为空串。

给出一棵Trie树,用来表示边上的口令。给出一条边口令时只会给出对应Trie树上的结点编号,口令就是从Trie树的根结点到这个点的字符串。

输出从1号点到其他点的最短距离。

多组数据$T \leq 10$,点数$\leq 5e4$,边数$\leq 5e4$,Trie树结点小于$\leq 2e4$

题解

是个毒瘤题也是个好题。

考虑直接暴力地建图。

对于上图,边数显然是$O(\max \deg(x)^2) \rightarrow O (m^2)$的,会爆炸。

问题是如何优化这个建图。

因为这个题中的点只起到联通作用,除此之外毫无意义,考虑把一条边拆成两个点,两个点之间链接一条有向边,边权为距离。

对于和一个点相连的$\deg$条边,每条边在Trie上对应一个点。

如果可以连出$O(\deg)$级别的边就可以解决问题。

那么可以把这些在Trie树上的点抽出来,建一棵虚树,这颗虚树的点数显然是$O(\deg)$级别的。

因为Trie上的LCP等于两点LCA的深度,那么可以枚举一个LCA,然后所有在当前点子树内的点和当前点的LCA为当前点;当前点两两子树之前的LCA为当前点。这个时候可以枚举一个子结点,这个子节点要和其他子节点连边,边权为当前点深度。由因为子树在dfs序上是连续的一段,这个子节点之外的其他的子树是两个连续的一段。把dfs序做出来以后就是在两个连续段之间连边,这个时候就是一个经典问题,可以使用线段树进行优化。把这$\log$个区间和$2 \log$个区间相连,新建一个辅助结点就可以把$O(\log^2)$降低到$O(\log)$。然后自己要和自己的子树连边,自己的子树也要和自己连边,方法类似。

其实理清思路以后难点就在代码实现了。

复杂度

考虑最极端的情况,$\max \deg$和$m$同级,那么会连出$\log m$条边,跑一遍最短路的总复杂度为$O(m\log^2m)$。

其实这个东西的常数爆炸,感觉比的上$\log$。

人垃圾,常数大,于是Luogu倒数第一和BZOJ倒数第三的代码就诞生了。

几个细节

  • 入边连入线段树的叶节点,出线段树的叶结点连出边。
  • 注意数组清零的时候的复杂度。(虚树相关)
  • 连区间的时候不能只连自己这个点,而是要连上自己的子树。
  • 存距离的时候要开long long。(不然90分)

注意代码细节,不然大数据WA了小数据A了对拍还要花很长时间。

感觉这题不可对着数据调试(所有测试数据都是2M+。

代码

不知不觉就300行了。

Leave a Reply

Your email address will not be published. Required fields are marked *