一道传递闭包裸题。tarjan+拓扑dp也很强而且貌似更快。本来想写的。

然而查题解的时候发现一个博主的一句话引起了我的共鸣。

bzoj上这道题rank前面都是1500B+的大佬，很快，几百ms，到了1600ms，，就发现了许多600B左右的代码。

后面还有10s+的不知道咋做的。bitset也没加吧（毕竟数据太小了）。

果断Floyd-Warshall传递闭包+bitset水过。

---

 

靠题面是jpg啊

Input

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

Output

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

Sample Input

3

010

001

100

Sample Output

9

HINT

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

---

顺便复习传递闭包（OI里的）。好像离散数学有啥玩意我当然是不会啦。

传递闭包就是说给你有向图一个（01矩阵还是边集都行），问两点是否可达。（因为是有向图所以存在A能到B反之不可的情况）。

首先把给的信息建成一个邻接矩阵。

开局只有一个01矩阵，能不能求出正解全看造化你会不会。

其实很简单。Floyd求最短路会叭，直接跑一遍。只要两点之间距离不是inf就说明可达呗！

有点炎爆砸帕奇斯的感觉。因为只是求是否可达，就不需要初始化成inf再跑最短路，

只要$f[i][j]=1$即i可达j，那么j能到的i必然也能到，所以直接在$f[i]$的bitset上再或一个$f[j]$的bitset。

至于循环顺序，和Floyd最短路一样，不知道为啥记住就好咯。

 

---

 

贴代码

#include
      
       using namespace std;const int mxn=2010;bitset
       
        g[mxn];int main(){    int n;scanf("%d",&n);    char s[mxn];    for(int i=1;i<=n;i++){        scanf("%s",s+1);        for(int j=1;j<=n;j++)        g[i][j]=s[j]-'0';        g[i][i]=1;    }    for(int k=1;k<=n;k++)    for(int i=1;i<=n;i++)    if(g[i][k])g[i]|=g[k];    int ans=0;    for(int i=1;i<=n;i++)    ans+=g[i].count();    printf("%d",ans);}