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
别的不说,祝楼主早日获得图灵奖,为国争光[强]
fffff
<!DOCTYPE html> <html lang="zh-cn"> <head> <meta charset="utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1" /> <title>关于有向无环图可达性统计的问题 - 博客 - a1b3c7d9的博客</title> <script type="text/javascript">uojHome = 'http://uoj.ac'</script>
fffff
<!-- Bootstrap core CSS --> <link type="text/css" rel="stylesheet" href="http://uoj.ac/css/bootstrap.min.css?v=2015.5.31" /> <!-- Bootstrap theme --> <link type="text/css" rel="stylesheet" href="http://uoj.ac/css/bootstrap-theme.min.css?v=2015.5.31" /> <!-- Custom styles for this template --> <link type="text/css" rel="stylesheet" href="http://uoj.ac/css/uoj-theme.css?v=2.33333" /> <!-- jQuery (necessary for Bootstrap\'s JavaScript plugins) --> <script src="http://uoj.ac/js/jquery.min.js"></script> <!-- jQuery autosize --> <script src="http://uoj.ac/js/jquery.autosize.min.js"></script> <script type="text/javascript"> $(document).ready(function() { $('textarea').autosize(); }); </script>
fffff
<!-- jQuery cookie --> <script src="http://uoj.ac/js/jquery.cookie.min.js"></script> <!-- jQuery modal --> <script src="http://uoj.ac/js/jquery.modal.js"></script> <!-- Include all compiled plugins (below), or include individual files as needed --> <script src="http://uoj.ac/js/bootstrap.min.js?v=2015.5.31"></script> <!-- Color converter --> <script src="http://uoj.ac/js/color-converter.min.js"></script> <!-- uoj --> <script src="http://uoj.ac/js/uoj.js?v=2020.05.17-3"></script> <!-- readmore --> <script src="http://uoj.ac/js/readmore/readmore.min.js"></script> <!-- LAB --> <script src="http://uoj.ac/js/LAB.min.js"></script> <!-- UOJ ico --> <link rel="shortcut icon" href="http://uoj.ac/pictures/UOJ.ico" />
fffff
<!-- MathJax --> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ showProcessingMessages: false, tex2jax: { inlineMath: [["$", "$"], ["\\\\(", "\\\\)"]], processEscapes:true }, menuSettings: { zoom: "Hover" } }); </script> <script src="//cdn.bootcss.com/mathjax/2.7.7/MathJax.js?config=TeX-AMS_HTML"></script>
fffff
<!-- shjs --> <link type="text/css" rel="stylesheet" href="http://uoj.ac/css/sh_typical.min.css" /> <script src="http://uoj.ac/js/sh_main.min.js"></script> <script type="text/javascript">$(document).ready(function(){sh_highlightDocument()})</script> <!-- HTML5 shim and Respond.js IE8 support of HTML5 elements and media queries --> <!--[if lt IE 9]> <script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script> <script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script> <![endif]--> <script type="text/javascript"> before_window_unload_message = null; $(window).on('beforeunload', function() { if (before_window_unload_message !== null) { return before_window_unload_message; } }); </script>
fffff
<script>var _hmt = _hmt || [];(function() {var hm = document.createElement("script");hm.src = "//hm.baidu.com/hm.js?bbd5ae87bf89e087603a1988103688ff";var s = document.getElementsByTagName("script")[0];s.parentNode.insertBefore(hm, s);})();</script> </head> <body role="document"> <div class="container theme-showcase" role="main"> <div> <ul class="nav nav-pills pull-right" role="tablist"> <li class="dropdown"> <a href="#" data-toggle="dropdown">
fffff
<span class="uoj-username" data-rating="1500" data-link="0">fffff</span> </a> <ul class="dropdown-menu" role="menu"> <li role="presentation"><a href="http://uoj.ac/user/profile/fffff">个人信息</a></li> <li role="presentation"><a href="http://uoj.ac/user/msg">私信&nbsp;&nbsp;</a></li> <li role="presentation"><a href="http://uoj.ac/user/system-msg">系统消息&nbsp;&nbsp;</a></li> </ul> </li> <li role="presentation"><a href="http://uoj.ac/logout?_token=BcnnndlCDq9rAdAEbpZLZTvVGDTYU2AvmhpPWWVeCmNzvIK5WfD2pKIUT5q4">登出</a></li> </ul> <h1 class="hidden-xs"><a href="http://uoj.ac"><img src="http://uoj.ac/pictures/UOJ_small.png" alt="UOJ Logo" class="img-rounded" style="width:39px; height:39px;" /></a>
fffff
a1b3c7d9的博客</h1> <h1 class="visible-xs">博客</h1> </div> <div class="navbar navbar-default" role="navigation"> <div class="container-fluid"> <div class="navbar-header"> <button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target=".navbar-collapse"> <span class="sr-only">导航</span> <span class="icon-bar"></span> <span class="icon-bar"></span> <span class="icon-bar"></span> </button> <a class="navbar-brand" href="/">a1b3c7d9</a> </div> <div class="navbar-collapse collapse"> <ul class="nav navbar-nav"> <li><a href="/archive">日志</a></li> <li><a href="/aboutme">关于我</a></li> <li><a href="http://uoj.ac">UOJ</a></li> </ul> </div><!--/.nav-collapse --> </div> </div>

发表评论

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