【bzoj2208】[Jsoi2010]连通数

2014年5月15日3,1294

Description

Input

输入数据第一行是图顶点的数量,一个正整数N。 接下来N行,每行N个字符。第i行第j列的1表示顶点i到j有边,0则表示无边。

Output

输出一行一个整数,表示该图的连通数。

Sample Input

3
010
001
100

Sample Output

9

HINT

对于100%的数据,N不超过2000。

题解

据说此题暴力是可过的,复杂度O(nm)

正解似乎是先缩点完然后递推

 

  • wulala2014年6月11日 上午11:38 回复

    后面那东西是叫传递闭包吧。。不过hzwer学长都说他是递推了就递推吧

    #1  
    • hzwer2014年6月11日 下午11:17 回复
      admin

      传递闭包。。唔我理解的传递闭包似乎是用floyd。。。不过你这么一说倒是想起来了

      #11
  • hahaha2016年7月10日 下午8:55 回复

    所以闭包到底是什么

    #2  
  • orzhzwer2016年7月10日 下午9:22 回复

    顺便问一下这个模数要怎么取(怎么得来的),比如数据范围是5000又该取多少

    #3