我乱想的,勿喷
(dfs)
从每条负变开始搜索,遇到岔路往负边走,若没有负边,就停止,换另一条路。如果最后回到了开始的那条边,就算成功
by fzfnf @ 2019-08-22 16:52:29
~~不是spfa也很简单么为毛还要用dfs~~
by 跃动の光は @ 2019-08-22 17:00:36
~~暴搜可以做任何题~~
by FZzzz @ 2019-08-22 17:03:27
@[跃动の光は](/space/show?uid=59545) ~~SPFA不是死了吗~~
by Computer1828 @ 2019-08-22 17:05:20
@[跃动の光は](/space/show?uid=59545) spfa的优化……简单么?
by 潜伏之OI @ 2019-08-22 17:06:17
## Bellman-Ford判负环
d[i]记录当前从1号点到i号点的最短路长度
d[1]初始为0,其他d[i]为INF
主循环:以下操作重复共n-1次
对于每一条边:从a到b,权重w
若d[a]+w<d[b], 则更新d[b]=d[a]+w
额外再循环1次
对于每一条边:从a到b,权重w
若d[a]+w<d[b], 则发现负环
by Frainstak @ 2019-08-22 17:08:25
@[潜伏之OI](/space/show?uid=57820) [SLF优化](https://www.cnblogs.com/mypsq/p/4403285.html)很简单
by 跃动の光は @ 2019-08-22 17:11:01
@[拥抱渴望者](/space/show?uid=114173) 可以加优化啊~~(虽然是玄学优化)~~
by 跃动の光は @ 2019-08-22 17:11:48
@[fzfnf](/space/show?uid=110663) 负环不一定全是负边
by yurzhang @ 2019-08-22 17:12:36
@[跃动の光は](/space/show?uid=59545) 优化我也能卡你
by 潜伏之OI @ 2019-08-23 07:46:36