负环.md

###负环
````
存在一个环,其边权之和小于0
只要一个点可以走到负环上,可以在负环上走无穷次,
使得权值和为无穷小

01分数规划

求负环的常见方法基于spfa
1.统计每个点入队的次数,如果某个点入队n次,说明存在负环
类似于BellmanFord
最差O(n^2)
推荐2.统计当前每个点的最短路中所包含的边数,
如果某个点的最短路所包含的边数大于等于n,
则也说明存在环
O(n)推荐

考虑1~n组成负环,第一种做法是O(n^2) n(n-1)+1次

初始化,queue加入所有节点,看做超级源点连接每个点权值都为0
dis不用初始化
如果有负环,dis赋值为有限值,一直减结果必然会变成负无穷

只有BellmanFord 和Floyd才有 0x3f3f3f3f/2

spfa判断环,把队列换成栈跑的更快