题解 | #[JSOI2010]连通数#
[JSOI2010]连通数
https://ac.nowcoder.com/acm/problem/20187
思路
bitset优化传递闭包模板。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn=2007;
bitset<maxn>bi[maxn];
int n,ans=0;
string str;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>str;
for(int j=1;j<=n;j++)
bi[i][j]=(str[j-1]=='1'||i==j)?1:0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(bi[j].test(i)) bi[j]|=bi[i];
for(int i=1;i<=n;i++) ans+=bi[i].count();
cout<<ans<<endl;
return 0;
}
