传统时间复杂度是$O(n+m)n/64$，询问在稠密图上怎么做到$O(n^2)$。
a1b3c7d9的博客
博客
关于有向无环图可达性统计的问题
2019-09-12 13:55:32 By a1b3c7d9
评论
r_64
只能用矩阵乘法做到$O(n^\omega)$吧？如果要问两两可达性的话，这个问题跟矩阵乘法应该是等价的。。。
- 2019-09-12 14:54:02
a1b3c7d9
好像有一个办法了，但是是$n^2log(n)$，帮忙hack一下。
- 2019-09-13 15:26:49
OldDriverTree
这不是和bool mat mul双向规约吗
- 2019-09-14 14:52:12
OldDriverTree
那稠密图目前只能O( n^2.373 )吧
- 2019-09-14 14:52:37
aji
别的不说，祝楼主早日获得图灵奖，为国争光[强]
- 2019-09-14 19:44:13
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>
- 2020-06-23 21:12:52
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>
- 2020-06-23 21:13:10
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" />
- 2020-06-23 21:13:37
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>
- 2020-06-23 21:13:57
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>
- 2020-06-23 21:14:16
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">
- 2020-06-23 21:15:01
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">私信 </a></li>
<li role="presentation"><a href="http://uoj.ac/user/system-msg">系统消息 </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>
- 2020-06-23 21:15:07
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>
- 2020-06-23 21:15:32
发表评论
可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。
- Universal Online Judge |
鄂公网安备 42010202000505 号
Server time: 2024-04-25 15:52:20