SPFA 学习笔记
SPFA学习笔记SPFA，他死了！——某次 noi T1 的出题人。感觉和 DIJ 很像。使用范围：负边权，判断负环，随机图不适用于构造图。容易超时。思路：对于出发的点，向所有可以到达，并且没到达过的点的边都进行松弛（见 图论—…
CATEGORY
学习笔记
这个分类下的文章与记录。20 篇内容
↗
Tarjan 求割点和桥
[alert]图片来自 https://sikats.us.to/tarjan-algorithm-find-strongly-connected-components/[/alert]Tarjan 求割点割点的定义关节点的定义…
拓扑排序与关键路径
拓扑排序介绍拓扑排序是一种将一个有向无环图变成一个线性序列的算法。这个序列的要求是：每个顶点都出现了一次。对于一条边：$a \to b$，我们要求 $a$ 在 $b$ 的前面。实现找到入度为 $0$ 的点，输出。删除这个点和这个…
模意义下的乘法逆元学习笔记
定义$a$ 的逆元写作 $a^{-1}$。我们定义 $a \times a^{-1} \equiv 1 \pmod p$。计算方法费马小定理知识链接欧拉定理 & 费马小定理 - OI Wiki (oi-wiki.org)费马小定…
树状数组
树状数组树状数组其实是一种针对于前缀和的优化。可以将区间查询和修改的复杂度讲从 $O(n)$ 降到 $O(\log n)$。算法主要思路正常的前缀和数组如果显示为一个树的话是这样的：也就是 $f_i$ 维护的区间是 $[1, i…