题解 CF590E 【Birthday】
xht
2020-01-27 18:13:02
> [CF590E Birthday](https://codeforces.com/contest/590/problem/E)
## 题意
- 给定 $n$ 个仅包含 `a,b` 的字符串。
- 你需要去掉尽可能少的字符串，使得剩下的字符串中不存在某一个串是另一个串的子串。
- $n \le 750$，$\sum_{i=1}^n |s_i| \le 10^7$。
## 题解
设 $\sum_{i=1}^n |s_i| = m$。
首先可以 $\mathcal O(m)$ 建 AC 自动机然后求出所有的子串关系。
显然我们不能暴力跳 fail，这样显然会 T 飞。
注意到子串关系是一个**偏序关系**，因此我们只需要跳到最近的结尾同时路径压缩即可，那么此时可以建出一个 DAG。
接下来就是 [P4298 [CTSC2008]祭祀](https://www.luogu.com.cn/problem/P4298)了，不过还是在这儿完整的写一遍。
题目要求的实际上是这个偏序关系的**最长反链**，通过 Dilworth 定理可以发现就是 DAG 的**最小可重复路径点覆盖**。
最小可重复路径点覆盖又可以通过 $\mathcal O(n^3)$ 的传递闭包转化为**最小路径点覆盖**。
又 DAG 的最小路径点覆盖包含的路径条数 $= n -$ 其**拆点二分图**的最大匹配数。
使用**匈牙利算法**即可在 $\mathcal O(n^3)$ 的时间求出答案。
接下来的问题是如何构造方案。
我们先求出传递闭包后的图的最小路径点覆盖包含的路径集合 $path$：
1. 设在拆点二分图中左部点 $x$ 对应的右部点为 $x^{\prime}$，若 $x,y$ 匹配则有 $f_x = y, f_y = x$。
2. 依次考虑左部的每一个非匹配点 $x_0$。
3. 从 $x_0$ 出发，每次从 $x$ 走到 $f_{x^{\prime}}$，直至到达一个左部点 $y_0$，满足 $y_0^{\prime}$ 是非匹配点。
4. 那么经过的所有点构成一条以 $y_0$ 为起点 $x_0$ 为终点的路径。
接下来我们要从 $path$ 的每条路径上选出一个点构成原图的最长反链：
1. 将所有的终点 $x_0$ 放到一起构成一个集合 $E$。
2. 求出从 $E$ 中的所有节点出发，走一条边，到达的所有节点 $next(E)$。
3. 根据传递闭包的性质，若 $E$ 与 $next(E)$ 没有交，那么 $E$ 即为所求。
4. 否则考虑 $E \cap next(E)$ 的所有节点 $e$，沿着 $e$ 所在的路径反着走，直到一个节点 $e^{\prime} \notin next(E)$，在 $E$ 中将 $e$ 替换为 $e^{\prime}$。
5. 回到第 $3$ 步。
总时间复杂度 $\mathcal O(m + n^3)$。
注意本题任何与 AC 自动机相关的递归均会爆栈。
## 代码
```cpp
const int N = 757, M = 1e7 + 7;
int n, len[N], ed[N], trie[M][2], fail[M], fa[M], gt[M], tot = 1;
int d[N][N], v[N], f[N];
char s[M];
queue<int> q;
bool dfs(int x) {
for (int i = 1; i <= n; i++)
if (d[x][i] && !v[i]) {
v[i] = 1;
if (!f[i] || dfs(f[i])) return (f[i] = x);
}
return 0;
}
int main() {
rd(n);
for (int i = 1; i <= n; i++) {
rds(s, len[i]);
int p = 1;
for (int j = 1; j <= len[i]; j++) {
int c = s[j] - 'a';
if (!trie[p][c]) trie[p][c] = ++tot, fa[tot] = p;
p = trie[p][c];
}
ed[i] = p, gt[p] = i;
}
for (int i = 0; i < 2; i++)
if (trie[1][i]) fail[trie[1][i]] = 1, q.push(trie[1][i]);
else trie[1][i] = 1;
while (q.size()) {
int x = q.front();
q.pop();
for (int i = 0; i < 2; i++)
if (trie[x][i])
fail[trie[x][i]] = trie[fail[x]][i], q.push(trie[x][i]);
else trie[x][i] = trie[fail[x]][i];
}
gt[1] = -1;
vi o;
for (int i = 1; i <= n; i++)
for (int j = ed[i]; j != 1; j = fa[j]) {
int x = fail[j];
o.clear();
while (!gt[x]) o.pb(x), x = fail[x];
while (o.size()) fail[o.back()] = x, o.pop_back();
fail[j] = x;
if (j != ed[i] && gt[j]) x = j;
if (x != 1) d[i][gt[x]] = 1;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] |= d[i][k] & d[k][j];
for (int i = 1; i <= n; i++) d[i][i] = 0;
int ans = n;
for (int i = 1; i <= n; i++) ans -= dfs(i), memset(v, 0, sizeof(v));
print(ans);
for (int i = 1; i <= n; i++) v[f[i]] = 1;
vi s;
for (int i = 1; i <= n; i++) if (!v[i]) s.pb(i);
memset(v, 0, sizeof(v));
bool ok = 1;
while (ok) {
ok = 0;
for (int x : s)
for (int y = 1; y <= n; y++)
if (d[x][y]) v[y] = 1;
for (int &x : s)
if (v[x]) {
ok = 1;
while (v[x]) x = f[x];
}
}
for (auto x : s) print(x, ' ');
return 0;
}
```