连通数 bzoj-2208 Jsoi-2010
题目大意：给定一个n个节点的有向图，问每个节点可以到达的点的个数和。
注释：$1\le n\le 2000$。
想法：网上有好多tarjan+拓扑序dp的...
我们考虑暴力怎么做：显然就是用floyd的warshall求出连通矩阵，然后扫矩阵即可。
发现这个过程可以使用bitset进行优化，复杂度为$O(\frac{n^3}{32})$。
最后，附上丑陋的代码... ...
#include <bits/stdc++.h>using namespace std;bitset<2010>bt[2010];char s[2010][2010];int main(){ ???int n; cin >> n ; for(int i=1;i<=n;i++) scanf("%s",s[i]+1); for(int i=1;i<=n;i++) ???{ ???????for(int j=1;j<=n;j++) if(s[i][j]==‘1‘||i==j) bt[i][j]=true; ???} ???for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) if(bt[i][j]) bt[i]|=bt[j]; ???int ans=0; for(int i=1;i<=n;i++) ans+=bt[i].count(); printf("%d\n",ans); ???return 0;}小结：有些时候看到二进制，而且复杂度并不优秀，考虑考虑bitset可能有奇效哦？！
[bzoj2208][Jsoi2010]连通数_bitset_传递闭包floyd
原文地址：https://www.cnblogs.com/ShuraK/p/9802199.html