首页 > 代码库 > [bzoj2208][Jsoi2010]连通数

[bzoj2208][Jsoi2010]连通数

来自FallDream的博客,未经允许,请勿转载,谢谢。


技术分享

n<=2000

bitset优化floyd , 枚举k,枚举i,如果i能到k,那么i的bitset直接或上k的。复杂度$O(\frac{n^{3}}{32})$

#include<iostream>#include<cstdio>#include<bitset>#define MN 2000using namespace std;inline int read(){    int x = 0 , f = 1; char ch = getchar();    while(ch < 0 || ch > 9){ if(ch == -) f = -1;  ch = getchar();}    while(ch >= 0 && ch <= 9){x = x * 10 + ch - 0;ch = getchar();}    return x * f;}int n,ans=0;char st[MN+5];bitset<MN+1> b[MN+2];int main(){    n=read();    for(int i=1;i<=n;i++)    {        scanf("%s",st+1);        for(int j=1;j<=n;j++)            b[i][j]=(st[j]==1||i==j)?1:0;        }    for(int k=1;k<=n;k++)        for(int i=1;i<=n;i++)            if(b[i][k]) b[i]|=b[k];    for(int i=1;i<=n;i++) ans+=b[i].count();    cout<<ans;    return 0;}

 

[bzoj2208][Jsoi2010]连通数