正题

题目链接:https://www.luogu.com.cn/problem/P4306

---

题目大意

n n n个点的有向图，求图上可以相互到达点数。

---

解题思路

就是 b i t s e t bitset bitset这个黑科技的模板，首先是传递闭包
f i , j = f i , k ∣ f k , j f_{i,j}=f_{i,k}|f_{k,j} fi,j​=fi,k​∣fk,j​也就是如果 f i , k f_{i,k} fi,k​那么有 f i , j ∣ = f k , j f_{i,j}|=f_{k,j} fi,j​∣=fk,j​

二进制数字 b i b_i bi​表示 i i i能够到达的点集合，然后如果 b i , j = 1 b_{i,j}=1 bi,j​=1那么 b i ∣ = b j b_i|=b_j bi​∣=bj​。

用 b i t s e t bitset bitset优化，时间复杂度 O ( n 3 32 ) O(\frac{n^3}{32}) O(32n3​)

---

c o d e code code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int N=2100;
int n,ans;char s[N];
bitset<N> b[N];
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s",s);
		for(int j=0;j<n;j++)
			b[i][j]=(s[j]=='1');
		b[i][i]=1;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(b[i][j])b[i]|=b[j];
	for(int i=0;i<n;i++)
		ans+=b[i].count();
	printf("%d\n",ans);
}