@[url=/space/show?uid=3182]Created\_equal1[/url]
说得有道理
不过我还不会求有环的最长路径
by kczno1 @ 2015-10-20 20:14:27
@[url=/space/show?uid=9168]kczno1[/url] 有向图中不一定存在最长路径，因为可能有正权环（这和当存在负权环时没有最短路径是一个道理）。而本题要求求的是有向图中简单最长路径，也就是不带环（不经过重复点）的最长路径，这是一个NP完全问题。。
by Created_equal1 @ 2015-10-20 20:52:13
@[url=/space/show?uid=3182]Created\_equal1[/url]
应该要选一个入度为0的点作起始点吧
by kczno1 @ 2015-10-21 17:56:43
然后每次都更新连接的点的最长路径，并减其入度
by kczno1 @ 2015-10-21 17:57:53
求最长路径的题我没学过也没做过
by kczno1 @ 2015-10-21 17:59:26
@[url=/space/show?uid=9168]kczno1[/url] 并不是。。你说的是有向无环图上的最长路径。。我说的是有向图上的最长简单路径。。
by Created_equal1 @ 2015-10-21 18:47:19
@[url=/space/show?uid=3182]Created\_equal1[/url] 求教
by kczno1 @ 2015-10-21 19:34:08
然而记忆化好打啊。。
而且好理解
by Dispwnl @ 2017-09-27 18:12:20
记忆化是错的吧我感觉
by Patrickpwq @ 2018-10-17 22:29:35
数据水了
by Patrickpwq @ 2018-10-17 22:29:43