floyd优化题目 bzoj2208

###### BZOJ2208 JSOI2010 ###### 蒟蒻来一发 滋滋 [题目](http://www.lydsy.com/JudgeOnline/problem.php?id=2208) 联通数 一道~~好像不很难~~的题 用了bitset 上代码吧 ```cpp #include<cstdio> #include<bitset> #include<iostream> using namespace std; int main(){ int n; int x; int ans=0; bitset<2050> di[2050]; scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%1d",&x); di[i][j]=x; } di[i][i]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(di[i][k]) di[i]|=di[k]; for(int i=1;i<=n;i++) { ans+=di[i].count(); } printf("%d\n",ans); return 0; } ``` ## 一个Floyd的优化 #### O（n^3/32） 时间复杂度约为O（n^3/32） 如果用int型储存则常数为32，如果用lang lang则常数为64 因为bitset是按位储存啊 优化过程是通过**位运算**进行异或操作 请注意floyd内循环的改变 大概就这样—— 很短