BZOJ 4484 [Jsoi2015] 最小表示

发布于 2017-06-13  116 次阅读


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

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


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

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

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

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

 


一个非常弱的准退役OIER