YZOJ P4259 [FJWC 2019] 不同的缩写

时间限制：1000MS      内存限制：262144KB

出题人：E.Space      难度：\(6.1\)

• 题目描述

在这个游戏中一共有 \(n\) 个角色。你需要编写一些关于这些角色的对话内容。

你打算用角色名字的一个非空子序列来作为它的简称。

当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。

你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。

• 输入格式

第一行一个正整数 \(n\)。

接下来 \(n\) 行，每行一个由小写字母组成的字符串，代表一个角色的名字。

不同的角色可能会有相同的名字。

• 输出格式

如果不存在一种分配简称的方案满足条件，输出 \(-1\)。

否则第一行输出一个正整数，表示最长的简称的最小长度。

接下来 \(n\) 行每行一个字符串，按顺序表示每个角色的简称。

若有多种方案满足条件，那么你可以输出任意一种。

• 样例输入

• 样例输出

• 数据规模与约定

保证 \(n \leq 300\) ，每个名字的长度不超过 \(300\)。

 

 

 

---

 

 

 

我校校队成员（gamerboy

首先要求的是长度最小，可以想到二分答案，因为长度比答案大的一定可以，比答案小的一定不行。

因为每个人都与缩写一 一对应，所以其实发现这是一个二分图匹配，用序列自动机爆搜出所有的子序列，使用Trie树判重，然后连边匹配。

这样点/边数很多，所以考虑 Hall 定理，那么大于 \(n\) 个对应字符串的子序列就没有继续搜索的必要了。

这样就有一个点数 \(O(n^2)\) 边数 \(O(n^2)\) 的图，跑 Dinic 的复杂度是 \(O(n^3)\)，总复杂度 \(O(n^3logn)\) 。

都知道 Dinic 跑不满，所以这题可以过。