题解 P6999 【[NEERC2013]Dictionary】

· · 题解

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)。