[bitset优化传递闭包][JSOI 2010] 连通数

#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] 连通数

原文：https://www.cnblogs.com/AEMShana/p/12439522.html