「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;
}

------ 本文结束 ------