解决的是一个类似于管道输送的问题。

假设现在有一个管道网络，一共有 $n$ 个节点，其中 $1$ 号点是源头，能源源不断地提供输送物；$n$ 号是接收点，接收所有到达的输送物；中间的节点是中转点，可以将受到的输送物送入其他的管道；管道有容量。求出能到达 $n$ 的最多输送物量。

求解网络最大流比较常用的算法是 Dinic，此外网络流常常利用建模思想来解决一些看似不好入手的题。看似不是图论的题

最大流算法

梦开始的地方：Ford-Fulkerson

树的定义

图论定义：无向无环连通图。

等价定义：无相连通图，$n$ 个点和 $n-1$ 条边；$n$ 个点和 $n-1$ 条边的图，任意两个点之间有且仅有一条简单路径可以到达……

更具体的来说，树是一张无向图 $\mathcal T=(V,E)$，其中 $|E|=|V|-1$ 且任意两个点都联通。同时定义有根树和无根树的概念：有根树在 $V$ 中有一个特殊元素 $root$ 作为整棵树的根，而无根树没有。对于有根树，定义点 $u$ 的深度 $dep_u=\operatorname{dis}(u,root)$。

直径、半径等问题

小事

什么？

$$1+2+3+\dots=-\dfrac{1}{12}$$

简单理解

什么乱七八糟的。

$1$ 是正数，$2$ 是正数，$3$ 是正数，……加起来能是负的？

线性代数

Uh-oh.

也就是说，只要多写写公式你的水平自然会提升。——离散小波变换°

矩阵和线性方程组

矩阵是什么。嘴巴嘴巴嘴巴

虚树是一种减少冗余、优化时间复杂度的树上问题优化。

在解决某些树上问题时，如果在多次询问中点数总体很大，但是解决问题的“关键点”数量很少，就可以利用虚树来将无用的点“剔除”，从而减少时间浪费。

构造虚树的方法

一般来说令关键点集合为 $V$，那么虚树包含着所有关键点和它们的 $\mathrm{LCA}$。虚树的边直接连接 $\mathrm{LCA}$ 和下面的点，而不再关心中间经过的点。

而构造虚树的一种常用做法就是利用单调栈维护虚树上的一条链。

咍咍。

前置知识

• 复数。
• 微积分。
• 泰勒展开。
• 牛顿迭代。
• 多项式加法。

乘法

定义 $n$ 阶单位根为 $\mathbf C$ 内 $x^n=1$ 的根，记作 $\omega_1,\omega_2,\dots,\omega_n$，其中 $\omega_n=1$。

模板 P4097

有 $n$ 次操作，每次操作如下：

1. 在平面内插入一条线段。
2. 查询某点最高的线段高度。

时间复杂度 $O(n\log^2 n)$，强制在线。

雕像爆炸的充要条件是“唔噗噗噗”。

这时候我们就称 “雕像爆炸” 可以推出 “唔噗噗噗”，同时 “唔噗噗噗” 也可以推出 “雕像爆炸”。这记作：

和符号 $\Leftrightarrow$ 被迫在一起的两个可怜的小东西有什么共同特征呢？我们一起来看看吧。

从左到右

给定一个周长为 $L$ 的圆，从一个点出发，有 $n$ 个黑白熊雕像，编号为 $1$ 到 $n$，第 $i$ 个雕像在顺
时针 $X_i$ 米处，如果你没有在 $T_i$ 秒内收集到这个黑白熊雕像，那么这个雕像就会发出“唔噗噗噗”
的声音然后爆炸。

斜率优化

斜率优化，一种优化 1D/1D 转移 dp 的方式，即将转移方程化为一次函数 $y=kx+b$ 的形式，再利用建模转化，将转移变成在某些数据结构上，比如单调队列、单调栈、李超树的操作，以此来优化转移时间复杂度。

一般来说（我感觉）斜率优化的转移方程里常常见到 $s_is_j$ 的形式。

例子：AT_dp_z Frog 3

容易写出 dp 方程

SA 数组

后缀数组维护了字符串每个后缀的大小关系。利用这个数组可以维护很多厉害的信息。

但是首先要求出 $sa,rk$ 数组。

$sa_i$ 表示 $s[i\dots n]$ 这个后缀的大小排名，而 $rk_i$ 代表排名为 $i$ 的开头位置。显然有 $sa_{rk_i}=rk_{sa_i}=i$。

首先一个暴力算法是显然的：将所有后缀字符串排序。时间复杂度为 $O(n^2\log n)$。这个速度肯定不能被接受，需要优化，可以使用倍增算法来优化。