自动搬运

查看原文

来自洛谷，原作者为

	JoshAlMan i人

搬运于2025-08-24 22:25:45，当前版本为作者最后更新于2020-12-17 23:47:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

给一些单词，要求建一棵节点最少的字典树，使字典序中包含给定所有的单词（单词路径在树上出现过）。

Solution

若 $a$ 是 $b$ 的子串，那么 $b$ 的限制强于 $a$，$a$ 可以删去。

接下来我们就得到了两两不包含的单词集。

考虑如果要把单词 $x$ 插入到当前字典序，可以找一个包含 $x$ 最长前缀的位置，这样可以添加尽量少的后缀凑满整个单词，并且这步并不影响后续单词加入，因为字典树能表示的串还是一样，因此是独立的。并且 $x$ 最长前缀一定仅属于一个字符串，否则即跨越了两个字符串，即 $x$ 包含那个字符串，这种情况已经去掉了。

因此对于两个单词 $a, b$，可以设 $w(a, b)$ 为把 $b$ 接在 $a$ 后面的最小花费，即 $len_b -$ $b$ 的前缀与 $a$ 能匹配的最长长度，这个东西可以 KMP 快速求，不过此题没有必要。

把这个东西看成一个有向图，这样构成一个联通的字典树 $\Leftrightarrow$ 该图联通。

枚举根，求最小树形图即可。

这题还要记录方案，考虑朱刘算法的定义，缩点的新边选择的意义是选择这条边，去掉原来的入边。每一层每种新边的选择对应选1杀1，因此每次新边可以新开一个编号，在最终状态，考虑每个选择编号对应上一层选择不选哪两条边即可。把边弄出来之后，需要构造字典树，这里注意每个点可能代表若干串的某个下标，而边的含义是某点要在某点的某处往伸，我是把边预处理成最靠近根的点的位置。

时间复杂度 $O(n^4)$。