O I

key_rA9 · 2019-11-11 13:48:51 · 个人记录

（NOIP又活了）

• 零、奇怪的码(ka)风(chang)

  • 毫无可读性的无脑压行
  • 能写逗号就写逗号
  • if(xxx)xxx; ==> (xxx)&&(xxx);
    右边的xxx可以加逗号执行多个表达式，但若返回值只返回最后一个，其中xxx为void类型有时会不行
  • != ==> ^
    只用于判断，不能直接赋值
  • int ==> register int
    除非语法错误
  • i++ ==> ++i
    单独运算使用，压行时不一定
  • c-'0' ==> (c&15)
    快读内使用，也可写成 (c^'0')

• 一、最短路

  Dijkstra

  思路是每次选最小还未标记的点标记，然后让他去更新周围的点，因为这个点的最短路已确定（正确性证明：请另请高明）。

  实现可以用堆优化，一个点每次被更新后可能确定最短路，所以再次入堆，可能入堆后再次被更新，可以懒惰删除：若取出点i在堆中的值(即用于比较的也是被更新入队时的值) ≠ d[i]，则说明这个点已经确定了，且已经确定的点不会被更新入队，所以没必要额外标记。

  SPFA

  直接每次在队列里取出对头去更新，更新后不在队列的就入队，直到队列为空。貌似更暴力。。。怪不得会死

  模版就不说了。首选 Dijkstra（无负权边），能不用SPFA最好不用，貌似还有某奆佬写出魔改版dijkspfa（十年 OI 一场空，SPFA 见祖宗）。打Dijkstra时注意手写堆，同样也是最好不用 STL（太慢），有必要节省多一些时间。

  顺便：二叉堆是一维数组实现类似树的结构，左孩子 i<<1，右孩子 i<<1|1，父亲 i>>1。以大根堆为例，基本操作如下：

  1. 读取最大：直接是 a[1]。

  2. 插入元素：直接将这个元素放在数组最后，然后从这最后一个点向上调整，即让他一直往上篡位直到父亲比他大，就停止，这维护了大根堆。

  3. 删除堆顶：用数组最后一个元素（记得删掉）代替堆顶，然后从堆顶向下调整，和上面差不多，但要让位给长子（较大），同样当无法继续调整时就停止。

• 二、并查集

  理解:处理集合之间可传递性关系的数据结构，例如；朋友的朋友也是朋友。

  关键要掌握“边带权”和“扩展域”运用（这才是重点），这篇写的不错。

  总之扩展域就是把所有点都分成 t 个点（t 一般为关系数），其中 i 的第j个点代表的意义是：与i是第j种关系的点所在的集合。但是每个并查集的意义并不具体指出谁到底属于哪个集合，只是说明里面所指的是同一个集合。

• 三、最小生成树

  有两种主流算法，Prim 和 Kruskal。目前学了后者。

  Prim用于稠密图，Kruskal 用于稀疏图。——某dalao

  所以有机会学下 Prim 吧。

  Kruskal 就是按边权从小到大排序，并查集一个个判断，如果两端点不在同一个集合里，就合并到同一个集合里然后将边加入生成树；否则继续判断下一条边。

• 四、树状数组

  码量清新，主要会求逆序对，会用差分实现区间修改，区间查询（有局限性）。

• 五、线段树

• 六、树形DP

• 七、树链剖分

  需要一颗线段树。

  数组：fa[i],dep[i],son[i],tot[i],top[i],ys[i]

  从左往右依次是：父亲，深度，重儿子，所在子树的节点数，所在重链起始点，新编号。

  主要函数：

  1. void dfs1(int x)建树函数，初始化前面四个数组，无需赘述；
  2. void dfs2(int x,int tp)给点重新编号并求top数组，对于每个点先给他一个新编号，接着top[x]=tp，然后遍历子节点时优先重儿子（轻儿子的tp是自己）。新编号让重链及子树的编号都是连续的，然后线段树：“嘿嘿嘿“。
  3. int solve(int x,int y)就是找LCA，顺便计算路径上的值，

• 八、LCA

  倍增找树上最近公共祖先，细节主要两个函数：

  1. void bt(int x,int fa)建树函数，初始化每个节点的层数、第1<<i个祖先的编号
  2. int lca(int x,int y)找LCA，先让下面的跳到同深度，再一起跳到LCA的子节点（当第1<<i个祖先不同时一起跳到这个祖先处），最后取他们共同的父亲。

• 九、二分图

  blog

  匈牙利算法：“暴力访问，能抢就抢”。核心在于记录每轮中母牛是否被访问过的数组。

  1. 二分图的最大匹配

  匈牙利算法

  2. 二分图的最小点覆盖=二分图的最大匹配

  3. 二分图的最少边覆盖=点数-二分图的最大匹配

  4. 二分图的最大独立集=点数-二分图的最大匹配

• 十、Tarjan

  无向连通图

  桥：边，删除后图不连通

  割点：点，将其与所有直连边删除后图不连通

  有割点不一定有桥，有桥一定存在割点
  桥一定是割点依附的边。

  时间戳(dfn)：深度优先遍历中第一次访问的时间顺序

  搜索树：深度优先遍历所有发生递归的边（y 第一次被访问）构成的树(就是遍历走出来的树)

  追溯值(low):通过一条不在搜索树上的边能够到搜索树中以x为根的子树的点中最小的时间戳，若无此点则为x的时间戳

  边双连通连通图：没有桥的无向连通图

  点双连通连通图：没有割点的无向连通图

  • 桥的判定法则

  搜索树中 x 的子节点 y，满足dfn[x]<low[y]

  dfs实现：dfn[x]和 low[x]赋值，遍历周围点，已搜索（有时间戳）的用dfn[y]更新low[x]；未搜索的就是搜索树中的子节点了，递归 y 后，low[y]更新low[x]，最后判断是否是桥

  当图中有重边且不能合并时，可以不记录采用无向图边的编号成对变换（x与x^1），每经过一条边，就把返回的边标记

  • 割点判定法则

  搜索树中 x 的子节点 y，满足dfn[x]≤low[y]，则 x 为割点，特殊地，当 x 为根节点时需要有两个 y 满足条件

  因为可以取等，所以可以low值可以用父节点更新（无影响）

  • 边双连通分量（e-DCC）

  将所有桥删除后剩下的各个连通块就是 e-DCC

  • 点双连通分量（v-DCC）

  和e-DCC类似，但是一个割点可能在多个 v-DCC 中，即相邻所有点所在的 v-DCC 都包含它。实现：dfs中第一次访问时入栈，每当有 x，y 满足割点条件时，弹出栈顶直到 y 被弹出，弹出的所有点和 x 一起为一个v-DCC

• 十一、网络流

  准备：层次数组，有反向边的图。

  Dinic过程：

  1. 建层次图，类似树的深度，但是用BFS，若源点不能到汇点则结束；
  2. DFS搜索存在的流加入总答案，源点出发尝试通过所有边分散流量（只能流到下一层），如果某点流不出则将层次设为0；
  3. 重复上面步骤。

  当前弧优化：对于每个点都从本次DFS中最后一次访问过的边开始搜索。

  费用流：

  1. 在还有流量的边中找源点到汇点的费用最短路，顺便记录这条路径能流过的最大流量，以及路径上每个点上一个点和边，若到不了就结束；
  2. 答案加上这条路径能流过的最大流量，费用即 这个流量*路径总费用，然后一直往前每条边减去这个流量；
  3. 重复上面步骤。

  最小割：一个权值和最小的边集，使割掉这个边集后源点无法到汇点。

  在单源单汇流量图中，最大流等于最小割。

• 十二、动态规划

  单调队列

  队头维护合法性，队尾维护单调性

  环形

  1. 断环成链
  2. 无法一次处理完的情况，补充情况(如更改初始化)再DP一次

• 十三、字符串算法

  HASH

  base常用质数：131、
  字符串哈希求区间hash值：h[r]-h[l-1]*p[r-l+1](h[i]：1~i的hash值，p[i]：base的i次方)

• 十四、状态压缩