北京游记Day5

发表于 | 分类于 |

一.最小树形图

1. 基础

  1. 定义

    最小树形图,就是给有向带权图中指定一个特殊的点 $ root $ ,求一棵以 $ root $ 为根的有向生成树T,并且T中所有边的总权值最小。

2. 朱刘算法

  1. 复杂度 $ O(VE) $

  2. 算法流程

    1. 对固定根 $ root $ 进行一遍 $ DFS $ 判断是否存在最⼩小树形图。

    2. 为除了了 $ root $ 之外的每个顶点选定一条最小的入边(用 $ pre[u] $ 记录顶点 $ u $ 最小入边的起点)。

    3. 判断2中构造的⼊入边集合是否存在有向环,如果不不存在,那么这个集合就是该图的最
      ⼩小树形图。

    4. 如果3中判断出现有向环,则消环缩点。设 $ (u,v,w) $ 表示从 $ u $ 到 $ v $ 的权为 $ w $的边。

      假设3中判断出的有向环缩为新顶点 $ new $ ,若 $ u $ 位于环上,并设环中指向 $ u $ 的边权是 $ ω[u] $ 。

      那么对于每条从u出发的边 $ (u,v,w) $ ,在新图中连接 $ (new,v,w) $ ,对于每条进⼊入u的边 $ (in,u,w) $ ,在新图中建⽴立边 $ (in,new,w-ω[u]) $ 。

      新图⾥里里最⼩小树形图的权加上旧图中被收缩的环的权和,就是原图中最⼩小树形图的权值。重复2,3,4。

    5. 中判断⽆无有向环,返回权值。

3. 平面图

二.字符串

1. AC自动机

2. 后缀自动机

  1. 自动机：

    1. 构成：

      1. $ alpha $ : 字符集

      2. $ state $ : 状态集合

      3. $ init $: 初始状态

      4. $ end $ : 结束状态集合

      5. $ trans $ : 状态转移函数

      6. $ trans $ 函数

      $ trans(s,ch) $ 表示当前状态是 $ S $ ,读入字符 $ ch $ 后的状态

      $ trans(s,str) $ 表示当前状态是$ S $ ,读入字符串 $ str $ 后的状态

      1. 杂项

      自动机A能识别的字符串就是所有使得 $ trans(init,x)∈end $ 的字符串x即为 $ Reg(A) $

      从状态S开始可被识别的字符串集合记为 $ Reg(S) $

  2. 后缀自动机

    1. 定义

      给定字符串 $ S $

      $ S $的后缀自动机(SAM)是能够识别所有 $ S $ 的所有后缀的自动机

      即 $ SAM(x)=True $ ,当且仅当 $ x $ 是 $ S $ 的后缀

    2. 最简单的实现

      后缀树:将所有后缀插入trie中

      $ O(n^2) $

      太菜了

    3. 最简状态后缀自动机

      1. 大小是线性的

      2. 假如我们得到了最简状态后缀自动机SAM

        $ ST(str)=trans(init,str) $

        令母串为S,他的后缀的集合为 $ Suf $ ,他的连续子串的集合为 $ Fac $

        从位置 $ a $ 开始的后缀为 $ Suffix(a) $

        $ S[l,r) $ 表示S中 $ [l,r) $ 区间构成的子串

        下标从 $ 0 $ 开始

        对于字符串 $ x $ ,若 $ x $ 不属于 $ Fac $ ,那么 $ ST(x)=null $

        对于字符串 $ x $ ,若 $ x $ 属于 $ Fac $ ,那么 $ ST(x)!=null $