BZOJ 2208 [Jsoi2010] 连通数


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

题意:给出一个有向图的邻接矩阵,求有多少组点对可以互相到达。


练习 bitset 的时候发现了这题...

bitset 优化传递闭包即可,\(O(n^3/32)\),由于数据水,可以卡过 (貌似并不慢)

正解是 tarjan 缩点后传递闭包,思想和实现都不困难,先不写了 (颓

 

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

转载:转载请注明原文链接 - BZOJ 2208 [Jsoi2010] 连通数


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

标签: , ,