schtonn

前置知识

存图方式（邻接表，邻接矩阵）,图的遍历（dfs，bfs）

引入

我们举个例子吧： 有一个毒瘤水管工，他会造水管，有一天他造了一个水管网络，就像一个图。其中有一个点只有出边，就是源点（起点），还有一个点只有入边，是汇点（终点）。

点之间有一些管子，管子 \(i\) 在一个单位时间内能流 \(c_i\) 的水，现在毒瘤水管工想知道，他的水管在一个单位时间内，从源点最多能运多少水到汇点。

前置知识

存图方式（邻接表，邻接矩阵），并查集。

引入

生成树，就是从一个包含 \(n\) 个节点的无向图中选中 \(n-1\) 条边，使得这些边构成一棵树，并包含图中的所有节点。

最小生成树，就是找到一种生成树，使得这个生成树的边权和最小。

前置知识

哈哈，简单到爆，没有。

引入

并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。

前置知识

必备：存图方式（邻接表，邻接矩阵），dfs序。 维护：线段树、树状数组、BST。

引入

树链剖分，简单来说就是把树分割成链，然后维护每一条链。一般的维护算法有线段树，树状数组和BST。复杂度为\(O(\log n)\)。

\(\texttt{Is KaTeX working?-IT WORKED!NICE!}\) \[a^b\] \[\left(\dfrac{a}{b}\right)\]

\(\alpha_\beta = \gamma_\delta\)