2018年7月 – Edgaru089的Blog

Tarjan 算法求强连通分量

概念：有向图中的一部分点，其中所有点都可以互相到达时，称为强连通分量。

把一个有向图中所有的强连通分量各缩成一个点后，剩下的图中没有环，是一个有向无环图（DAG）。有向无环图拓扑序一定，可以进行图上dp/记忆化搜索等操作而不用担心后效性的问题。

大概是写给我自己看的

开始阅读之前，请确保您已完全理解普通线段树的工作原理。

思想：在线段树的基础上维护多个历史版本。

支持操作：在任意一个历史版本上的区间查询，基于任意一个历史版本的单点修改

自适应性辛普森法通过取区间左右端点和区间中点三点的函数值拟合二次函数的方式近似计算一段区间内的积分值，若与之前计算的值差别较大则将区间分为两份后递归计算。

将树上的点按照一定方式分为许多条链，从而将在树上的区间操作转移到线性数据结构上，减少时间复杂度的同时维护许多有用的信息。

常用的剖分依据有重链剖分，实链剖分（Link-Cut Tree）等。一般称重链剖分为树链剖分。

为流量网络中的每一条边赋予一个单位流量代价，在求最大流的基础上求最小代价的问题称为最小费用最大流问题（一般也称为费用流问题）。

求最大流的Edmonds-Karp算法通过广度优先搜索寻找增广路。
求费用流时，将广搜改为SPFA，求一条总单位开销最小的增广路，这样就可以保证方案总开销最小的同时流量最大。

在有向流量网络上求从源点到汇点的最大可能流量的问题，称为网络流问题。
流量网络中一些边的流量已被部分占用时，称其为残量网络。
在残量网络中一条从源点到汇点的有有效流量的路径称为增广路。

思想：通过不断以特殊方式将节点提升至根节点的方式，使二叉搜索树在随机数据下保持相对平衡。

特殊方式：由Tarjan提出的改进，在不断旋转一个节点的同时，若父亲和祖父节点在同一方向时，则先旋转父亲再旋转自己。