正解是tarjan强联通缩点，然而我意外地发现Floyd压位轻松过
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <cstdio>unsigned f[2000][63];int N;int gc(){ char c=getchar(); while (c!='0'&&c!='1') c=getchar(); return (int)c-48;}int count(unsigned x){ int res=0; while (x) res++,x&=(x-1); return res;}int main(){ scanf("%d",&N); for (int i=0;i<N;i++) { for (int j=0;j<N;j++) { int t=gc(); if (t) f[i][j/32]|=(1<<(j%32)); } f[i][i/32]|=(1<<(i%32)); } for (int k=0;k<N;k++) for (int i=0;i<N;i++) if ((f[i][k>>5]>>(k&31))&1) for (int j=0;j<=(N-1)>>5;j++) f[i][j]|=f[k][j]; int OUT=0; for (int i=0;i<N;i++) for (int j=0;j<=(N-1)/32;j++) OUT+=count(f[i][j]); printf("%d\n",OUT); return 0;} |
评论 (0)
