- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <bitset>
- using namespace std;
- #define RG register int
- #define LL long long
- bitset<2010> Mat[2010];
- int N;
- void Floyd(){
- for(RG i=1;i<=N;++i)
- Mat[i][i]=1;
- for(RG i=1;i<=N;++i)
- for(RG j=1;j<=N;++j)
- if(Mat[j][i]) Mat[j]|=Mat[i];
- return;
- }
- string temp;
- int main(){
- scanf("%d",&N);
- getline(cin,temp);
- for(RG i=1;i<=N;++i){
- for(RG j=1;j<=N;++j){
- char c;scanf("%c",&c);
- if(c=='1') Mat[i][j]=1;
- }
- getline(cin,temp);
- }
- Floyd();
- int Ans=0;
- for(RG i=1;i<=N;++i)
- Ans+=Mat[i].count();
- printf("%d\n",Ans);
- return 0;
- }
[bitset 优化传递闭包][JSOI 2010] 连通数
来源: http://www.bubuko.com/infodetail-3451898.html