简介 最小生成树问题是指用图中所有节点构造一个边权重之和最小的树，可以用 Prim 算法和 Kruskal 算法解决稠密图和稀疏图的最小生成树问题。 Prim 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。 求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。 Prim 算法适用于稠密图，与 Dijkstra 算法思想一致，基本思路如下 ...

简介 对于最短距离问题，一共有如下几种算法： Dijkstra 算法是用来计算单源正权最短路算法，它的朴素版适用于稠密图，复杂度 O(n2)O(n^2)O(n2)；堆优化版适合稀疏图，复杂度 O((n+m)log⁡n)O((n+m)\log n)O((n+m)logn)。 Bellman-ford 算法用来解决**（有边数限制）的含负权最短路问题**，如果有边数限制一般就只能用此算法求解，复杂度 ...

简介 该数据结构的作用有如下两点： 合并两个集合。 查询两个元素是否在同一个集合中。 基本实现原理是把每个集合用一颗树表示，树根的编号是这个集合的编号，每个节点都存储它的父节点，p[x] 表示 x 的父节点，对于根节点，p[x] = x。 对于优化，可以在查找树根时将路径上的每一个节点的父节点都指向树根。 例题 一共有 nnn 个数，编号是 111 ~ nnn，最开始每个数各自在一个集合中。 ...

Trie 树是用来存储和查找字符串或数字等构成元素不多的数据结构，多用来匹配特定前缀。

在 C++ 中用数组来模拟单双链表，这样的方式也被称为静态链表，下面以两例题记录 C++ 中的链表应该如何定义和使用。

简介 堆是一种完全二叉树（从上到下，从左到右排列）这意味着它可以被储存到一个数组中，并且对任意一个节点 iii 都有左子节点为 2i2i2i，右子节点为 2i+12i+12i+1，和线段树类似。 当插入元素时，我们需要下滤操作来维持堆的单调性，具体操作流程如下： 将当前节点和两个子节点作比较，如果满足单调性不做任何调整。 如果不满足将较小的子节点与父节点交换，使较小的子节点在上面。 递归执行将放 ...

前缀和用来求一个区间内的和，差分用来对一个区间加减常数的操作减少复杂度，利用了高中数学中学过的数列前N项和的性质。

高精度的实现模板，包括存储、运算、以及关于边界处理的分析。

配置文件 本文用 Dayjs 来处理日期。当然，完全可以用原生 Date，但我不想把时间浪费在处理日期上面。 我使用的是 butterfly 主题。如果读者正在使用别的主题，请查阅对应官方文档寻找如何插入自定义标签与自定义页脚信息。 在主题配置文件（即_config.butterfly.yml）中引入： 12345inject: bottom: - <script src=" ...

弧微分 这里简要给出过程，虽然不是特别严谨，但理解起来容易就好。 对于上图可以得出： ΔsΔx=∣AB⏠∣Δx=∣AB⏠∣2∣AB∣2⋅∣AB∣2(Δx)2=∣AB⏠∣2∣AB∣2⋅(Δx)2+(Δy)2(Δx)2=∣AB⏠∣2∣AB∣2⋅[1+(ΔyΔx)2]\begin{aligned} \frac{\Delta s}{\Delta x} &= \frac{|\overgroup{A ...