F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 3281 >> 题面有误,实际数据不全是DAG
zxyoi @ 2019-01-19 10:09:11
[ Quote ] [ Edit ] [ Delete ] 1#
本来是我lengauer-Tarjan都AC了,但是另一种完全基于DAG的算法一直WA。

我就写了一个拓扑排序,结果assert一下就RE,发现没有达到n个节点进入队列,说明不是DAG。

那么唯一正确的解法就只有lengauer-Tarjan+双指针前后缀DP了吧。

本来还有很多基于DAG的操作可以将复杂度里面$O(n+m)$的部分优化成$O(n)$的,可惜了
[Top] [Previous Page] [Next Page]

HOME Back