「Bzoj 2208」「Jsoi2010」连通数(Bitset)

BZOJ 2208
题意：求无向图中每个点能到点的个数。

显然传递闭包模板，这里类似CH2101，这题是无向图而且数据范围小。所以可以尝试暴力。

暴力是$n^3$的，用 $bitset$ 优化即可达到 $\frac {n^3}{32}$

具体就是将邻接矩阵存在$bitset$中, 枚举每个点$i$，然后找能到$i$的$j$，$i$能到的$j$也能到，所以把$i$的$bitset$并给$j$

知识点：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    bitset<2005 > bs[2005];

    int n;

    void clean() {
    }
    int solve() {

        clean();

        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) 
        for (int x, j = 1; j <= n; ++j) scanf("%1d", &x), bs[i][j] = x;

        for (int i = 1; i <= n; ++i) bs[i][i] = 1;

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (bs[j][i]) bs[j] |= bs[i];

        int ans = 0;
        for (int i = 1; i <= n; ++i) ans += bs[i].count();

        cout << ans;

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}