SPFA 学习笔记
SPFA学习笔记SPFA，他死了！——某次 noi T1 的出题人。感觉和 DIJ 很像。使用范围：负边权，判断负环，随机图不适用于构造图。容易超时。思路：对于出发的点，向所有可以到达，并且没到达过的点的边都进行松弛（见 图论—…
TAG
算法
使用这个标签归档的内容。11 篇内容
↗
Tarjan 求割点和桥
[alert]图片来自 https://sikats.us.to/tarjan-algorithm-find-strongly-connected-components/[/alert]Tarjan 求割点割点的定义关节点的定义…
模意义下的乘法逆元学习笔记
定义$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…
拓扑排序
前置知识DAG，是有向图（有向无环图）的简称。拓扑排序的定义如果 DAG 的一个遍历序列满足：每个点都访问了一遍。对于每个便，出发节点在目的地节点的前面输出。求拓扑排序定义 $d_i$ 为第 $i$ 个节点的入度。用邻接表储存一…