search

lydrainbowcat / tedukuri

《算法竞赛进阶指南》资源社区
2.35k stars 601 forks source link

P348 最优贸易 用SPFA的时间复杂度是正确的吗 #45

Closed YOYO-UIAT closed 4 years ago

YOYO-UIAT commented 4 years ago

有可能被特殊数据卡成 $O(nm)$ 的吧。

lydrainbowcat commented 4 years ago

那用啥。用Dijkstra是错的，参考https://github.com/lydrainbowcat/tedukuri/issues/19和https://www.acwing.com/solution/AcWing/content/3709/

YOYO-UIAT commented 4 years ago

@lydrainbowcat 好像可以缩点+dp

YOYO-UIAT commented 4 years ago

SPFA随便卡卡就挂了，具体看 https://www.luogu.com.cn/discuss/show/238359，yxc的题解也过不了

YOYO-UIAT commented 4 years ago

供测试的题目：https://www.luogu.com.cn/problem/U122279

lydrainbowcat commented 4 years ago

大家都知道SPFA复杂度会挂呀，但本题只是作为最短路的例题，还没讲到缩点。你可以认为数据范围没那么大，或者数据就是NOIP官方的数据。