保存帖子
发现
索引
热门
陶片放逐
关于
有关本题 SPFA 判负环的注意事项
板块
P3199 [HNOI2009] 最小圈
楼主
wsyhb
当前回复
2
已保存回复
2
发布时间
2021/7/14 11:48
上次更新
2023/11/4 14:50:34
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
有关本题 SPFA 判负环的注意事项
wsyhb
楼主
2021/7/14 11:48
用 DFS 代替 BFS,因为这样更容易找到环。
用每个点为起点进行 DFS 代替建立以向所有点连边的虚拟源点为起点进行 DFS,大概是本题只卡了后一种。
即使这样,时间复杂度也是错的(可以被卡爆),不过由于出题人没有卡,再加上标签都已经变成 DFS/SPFA/分数规划,遵循上述原则可以把本题当做板题……
2021/7/14 11:48
加载中...