补写。
学了学用bitset优化floyd，做这题比用强联通缩点+DP方便多了。
bitset具体就是一串编码，比如说定义bitset<2100>b，b就是一个2100位的01串。
由于位运算的存在，那么folyd的时候可以省掉一个j的循环，直接用整个串和另一个串做或运算
就像这样
for(int k=1;k<=n;k++)
??????? for(int i=1;i<=n;i++)
??????????? if(g[i][k]==1)g[i]|=g[k];
然后用count可以很快求出串中1的个数
这题就完了。
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<bitset>using namespace std;bitset<2100>g[2100];char ss[2100];int main(){ ???int n; ???scanf("%d",&n); ???for(int i=1;i<=n;i++) ???{ ???????scanf("%s",ss+1); ???????for(int j=1;j<=n;j++) ???????????if(i!=j) ???????????????g[i][j]=ss[j]-‘0‘; ???????????else ????????????????g[i][j]=1; ???} ???for(int j=1;j<=n;j++) ???????for(int i=1;i<=n;i++) ???????????if(g[i][j]==1)g[i]|=g[j]; ???int ans=0; ???for(int i=1;i<=n;i++)ans+=g[i].count(); ???printf("%d\n",ans); ???return 0;}bzoj2208: [Jsoi2010]连通数
原文地址：https://www.cnblogs.com/AKCqhzdy/p/8446121.html