Description
Input
输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。
Output
输出一行一个整数，表示该图的连通数。
Sample Input
3
010
001
100
010
001
100
Sample Output
9
HINT
对于100%的数据，N不超过2000。
Source
第一轮
题解
这道题刚看到就想到暴力，时限有20s，dfs可以A
但是dfs有些慢，我们想一些更优的算法
这道题就是让我们求传递闭包
所以我们可以用bitset来优化floyd
1 #include<bits/stdc++.h> 2 #define N 2005 3 using namespace std; 4 int n,x,ans; 5 bitset<N>flag[N]; 6 char st[N]; 7 int main(){ 8 ????scanf("%d",&n); 9 ????for (int i=1;i<=n;i++){10 ????????scanf("%s",st+1);11 ????????for (int j=1;j<=n;j++)12 ????????????if (st[j]==‘1‘||i==j) flag[i][j]=true;13 ????}14 ????for (int j=1;j<=n;j++)15 ????????for (int i=1;i<=n;i++)16 ????????????if (flag[i][j]) flag[i]|=flag[j];17 ????for (int i=1;i<=n;i++)18 ????????ans+=flag[i].count();19 ????printf("%d\n",ans);20 ????return 0;21 } BZOJ-2208-[Jsoi2010]连通数（bitset+floyd）
原文地址：http://www.cnblogs.com/zhuchenrui/p/7807885.html