链式前向星模板
一种图的表示方式,在无向图中编号为x和x^1的边是u->v和v->u
> 带权并查集:在维护并查集时维护其他信息
> e.g. 点x到father[x]的长度
最小生成树KRUSCAL
> 时间复杂度O(mlogm) 适用于稀疏图
> 将所有边递增排序后依次遍历
> 如果u, v已经联通那么continue
> 否则将边添加进图中使得u, v联通
最小生成树PRIM
> 时间复杂度O(n^2)或O(mlogm)
> 随便选一个点开始
> 用优先队列或枚举选出联通的权值最小的边
> 重复操作直到所有点都联通
01分数规划
> 求(a1+a2+a3+a4 ... an)/(b1+b2+b3+b4...bn)最大值的二分算法
> (a1+a2+a3+a4)/(b1+b2+b3+b4) >= mid
> a1+a2+a3+a4 >= mid(b1+b2+b3+b4)
> check函数就变成了:a1-midb1+a2-midb2... >= 0
康托展开 -> 排序的映射
a[i] 代表i位后比s[i]小的个数
hash = a[1](n-1)! + a[2](n-2)! + a[3]*(n-3)! ... a[n]*0!
> 在菊花图下SPFA退化为Bellman Ford,最坏时间复杂度为O(n^2)
DIJKSTRA 稀疏图 O(MLOGM) 模板
> 思路:反向建图,多层图
TARJAN算法:有向图的联通分量问题
> dfn[x] 表示点x的DFS序成树编号
> low[x] 表示x的子数的low[v]最小值
Tarjan求联通分量模板:
Tarjan求割桥问题模板:
Tarjan求割点问题模板
Tarjan缩点模板:
差分约束系统
> 若存在点1到x的最短路,则对于任意点y,存在dist[1][x]<=dist[1][y]+dist[y][x]
> 超级原点,汇点:一个假的点连着所有其他的点,有时可以简化代码量
> 树形DP思路:换根法,二次扫描法
欧拉序求LCA
> 初始化O(mlogm),查询O(1)
> lca(a, b) 为a, b在欧拉序第一次出现的区间内最浅的点
重链剖分
> 将树分为轻链和重链,访问时先访问重链,再根据dfn序构造线段树
> 实现从a -> b节点之间的O(logn)区间修改
> 一棵树最多被分成logn个重链
AC 自动机
> 一种状态自动机,在字典树的基础上加上了类似于kmp的fail的逆边
> 可以在文本串中查询多个文字串出现的次数和位置
> 复杂度O(lent+sum(lens))O(len_t+sum(len_s))O(lent +sum(lens ))
模板:
O(N) 欧拉筛求质数
O(N) 求欧拉函数 / 其他积性函数
高斯消元
> 模拟用消元法解n元一次方程,复杂度O(n^3)