首页 > 代码库 > [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]连通数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。