BZOJ2208 (连通数)[bitset, Floyd]

发表于 | 更新于 | | 阅读次数：

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2208

其实这题可以用Floyd…
用bitset跑Floyd传递闭包处理出每一对点之间的连通关系，然后$O(n^2)$枚举两个点之间是否连通计数即可。
感觉bitset常数还是比较小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
const int maxn=2009;
bitset<maxn> g[maxn];
char s[maxn];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        memset(g,0,sizeof(g));
        for(int i=0;i<n;i++) {
            scanf("%s",s);
            g[i][i]=true;//this is true when using floyd
            for(int j=0;s[j]!='\0';j++)
                if(s[j]=='1') g[i][j]=true;
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(g[j][i]) g[j]|=g[i]; // cant swap i and j
            }
        }
        int ans=0;
        for(int i=0;i<n;i++) {
            ans+=g[i].count();
        }
        printf("%d\n",ans);
    }
}