Atcoder abc354

https://atcoder.jp/contests/abc354

G - Select Strings

n个字符串si,每个字符串有价值ai,选一个字符串集合，使得集合中两两没有子串(连续)关系, 求最大价值和

n 100

sum |si| 5000

ai [1,1e9]

2s

1024mb

我的思路

这字符串可以 kmp si#s0#s1#s2.. 计算出 是否是子串关系

但之后怎么求不知道了

如果是依赖的选择 可以转化成 网络流

这里是互斥的选择

题解

Dilworth 定理(abc237ex做过): 有限偏序集S的宽度 = 最小链覆盖

所以变成求链覆盖, abc237ex的是没有权重的，就只需要选点数

注意到在 图中的每个点出度入度 只能是0,1 这和二分图匹配是一致的

每个点拆分成 出点和入点，那么每一次匹配(出u->入v) 对应原图的同样位置u->v 的一条边, 所以小链覆盖 = 总点数 - 最大二分图匹配

---

这里有了权重, 而且很大

这样建立 S->i_in->j_out->T

• S->i_in 容量 $A_i$
• >i_out->T 容量 $A_i$
• i_in->j_out 容量无穷大，如果 字符串i 包含 字符串j

这里 也就是

• 割断 S->i_in 的意思是 最优方案中存在 i的子串，所以i不选
• 割断 i_out->T 的意思是 i是 最优方案某个串的子串，所以i不选
• 中间无穷大 表示， i和j至少有一个不选

因为这里的 偏序（传递性）的关系，对于同一个i，不会同时割断S和T, 因为

S->k_in->i_out->T 如果割断out，说明存在一个 未割断k_in，否则不需要割断i_out
S->i_in->j_out->T 如果割断in ，说明存在一个 未割断j_out, 否则不需要割断i_in

而这种情况下 一定有

S->k_in->j_out->T 而这至少割断一个， 矛盾

总结,参考

emmm 好像做过，搜了一下 abc237遇到过, 整理到 /algo 下了

所以 后面感觉和dilworh又不是很有关？

这类总结是 对于有偏序的互斥的权重选择 依然是使用网络流，然后利用的是 拆in，out，考虑不被选择

没有偏序的这样拆好像满足不了上面割的性质