UOJ Logo a1b3c7d9的博客

博客

关于有向无环图可达性统计的问题

2019-09-12 13:55:32 By a1b3c7d9

传统时间复杂度是$O(n+m)n/64$,询问在稠密图上怎么做到$O(n^2)$。

评论

r_64
只能用矩阵乘法做到$O(n^\omega)$吧?如果要问两两可达性的话,这个问题跟矩阵乘法应该是等价的。。。
a1b3c7d9
好像有一个办法了,但是是$n^2log(n)$,帮忙hack一下。
OldDriverTree
这不是和bool mat mul双向规约吗
OldDriverTree
那稠密图目前只能O( n^2.373 )吧
aji
别的不说,祝楼主早日获得图灵奖,为国争光[强]

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。