负环

一般会与01分数规划结合。

基本定义：一个有向图或无向图中权值和小于0的环。

求负环的方法

基于SPFA

1. 统计每个点入队的次数，如果某个点入队n次，则说明存在负环

等价于Bellman-Ford算法

1. 统计当前到每个点的最短路中所包含的边数，如果某个点的最短路包含的边数大于等于n，说明存在负环

:::danger Trick: 当所有点的入队次数超过2n时，我们就认为图中有很大可能是存在负环的。 :::

1. 裸题

AcWing 904. 虫洞
spfa找负环
时间复杂度：最坏情况下O(nm)

2. 01分数规划

AcWing 361. 观光奶牛
结合二分，转换成找正环问题，通过用spfa找最长路即可。
还有一个技巧，点权放到出边上，方便处理。

二分找最大值使得能找到一个环满足下式

转换一下，点权转移到边权上得：

即用SPFA判断是否存在正环，最短路变为最长路即可
每条边的边权就是括号内的表达式的值。

AcWing 1165. 单词环
二分 + SPFA
一个技巧：点边对偶建图
SPFA优化：如果总更新入队数超过2n（n指节点数），认为其存在负环。（玄学！！）
另一种优化方式是：对于找负环一类的题目，把队列改成栈