BZOJ 4484 [Jsoi2015] 最小表示


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4484

题意:对于一个 DAG,最多能删除几条边使得不改变原图的连通性?


首先删除了后面的边一定不影响前面的连通性,然而相反不行,所以删除后面的边至少不会更差,我们按照拓扑序倒着删边

考虑枚举每个点的情况,当删除以点 i 为出点的边时,考虑有哪些点是必须保留的,按照拓扑序正着考虑,因为我们保留拓扑序小的边一定不会比保留大的更差,对于一条边,如果在加入它之前连通性仍能保证,就删除它,否则留下加入边集,重新统计联通性。

这样复杂度的瓶颈在于如何快速统计连通性,bitset 优化传递闭包即可...

实际的复杂度我也不会算... 当作\(O(能过)\) 好了 (update: 大概上界是\(O(\frac{n^2log_n}{32})\)

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4484 [Jsoi2015] 最小表示


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , , ,