【水题记录】JSOI2010 连通数
link
洛谷上的题解的做法似乎有点麻烦。（不得不说时限 300 ms ）
这里我们看了题后我们可以选择传递闭包做法。
但是时限太短，我们可以利用 bitset 优化。
明显会被 hack ，但是都 2023 了，NOIP 已经允许开 O2 了
然后……
就过了。
代码：
#include<iostream>
#include<string>
#include<bitset>
#define P(A) A=-~A
#define Fione(i,a,b) for(register int i=a;i<b;P(i))
const int NUMBER1=2000;
std::bitset<NUMBER1+5>a[NUMBER1+5];
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n,ans(0);
std::string s;
std::cin>>n;
Fione(i,0,n){
std::cin>>s;
Fione(j,0,n){
a[i][j]=s[j]-'0';
if(i==j)a[i][j]=1;
}
}
Fione(k,0,n)Fione(i,0,n)if(a[i][k])a[i]|=a[k];
Fione(i,0,n)ans+=a[i].count();
std::cout<<ans;
return 0;
}
后记：
lxl Orz