SPFA学习笔记 SPFA，他死了！——某次 noi T1 的出题人。 感觉和 DIJ 很像。 使用范围：负边权，判断负环，随机图 不适用于构造图。容易超时。 思路： 对于出发的点，向所有可以到达，并且没到达过的点的边都进行松弛（见 图论——dijkstra），将松弛的点入队，注意是队列不是优先队列。 继续重复上面的操作，直到队列为空。 #incl…

介绍了 Tarjan 求割点和桥。

模意义下的乘法逆元

树状数组学习笔记。

拓扑排序的介绍。

快速幂是一种基于二分思想运算幂的算法。

ST 表 ST 表运用了倍增的思想。 其中 $dp_{i, j} = \max(i \to i + 2^j - 1)$，也就是 $dp_{i, j}$ 的值是区间 $[i, i + 2^j - 1]$ 中的最大值。 通过上面的定义，显然 $dp_{i,0} = \max(i \to i + 2^0 - 1) = \max(i \to i) = a_…

欧拉回路和欧拉路径的总结

BFS、DFS 和图的储存与最短路算法。

LCA 是最近公共祖先的简称。 朴素算法 如果两个点的深度相同：就往上跳，直到两个节点相同。 否则先让两个点的深度相同。 倍增 和朴素算法类似，只是把挨个往上跳变成每次跳 $2^i$。 代码： #include <bits/stdc++.h> using namespace std; /* */ int n, m, s; vector …