Kosaraju算法，然後bitset優化
主要是學習一下自寫bitset的姿勢
#include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #define rep(i,l,r) for(int i=l;i<=r;i++) #define dow(i,l,r) for(int i=r;i>=l;i--) #define rep0(i,r) for(int i=0;i<r;i++) #define repedge(i,x) for(int i=cur[x];i>=0;i=e[i].next) #define maxn 550 #define maxm 100100 #define LL long long using namespace std; int tot,p[maxn],n,m,kk; char s[maxn]; struct Bitset{ unsigned int v[8]; void reset() //clear { memset(v,0,sizeof(v)); } void set(int x) //set v[x]=1 { v[x>>5]|=1u<<(x&31); } void flip(int x) // rev { v[x>>5]^=1u<<(x&31); } bool ask(int x) // is == 1? { return v[x>>5]>>(x&31)&1; } }vis,g[maxn],rg[maxn]; //vis[] =1 not vis,=0 vis //g[i][j] =1 exist i->j,=0 not exist //rg[i][j] =1 exist j->i,=0 not exist; void add(int j,int k) { g[j].flip(k); rg[k].flip(j); } int nlz(unsigned int x) { int n; n = 1; if ((x >> 16) == 0) {n = n +16; x = x <<16;} if ((x >> 24) == 0) {n = n + 8; x = x << 8;} if ((x >> 28) == 0) {n = n + 4; x = x << 4;} if ((x >> 30) == 0) {n = n + 2; x = x << 2;} n = n - (x >> 31); return 31-n; } void dfs0(int x) { vis.flip(x); rep0(i,8) { unsigned int now=vis.v[i]&g[x].v[i]; while (now) { dfs0(i<<5|nlz(now)); now=vis.v[i]&g[x].v[i]; } } p[++tot]=x; } void dfs1(int x) { vis.flip(x); ++tot; rep0(i,8) { unsigned int now=vis.v[i]&rg[x].v[i]; while (now) { dfs1(i<<5|nlz(now)); now=vis.v[i]&rg[x].v[i]; } } } int calc() { vis.reset(); rep0(i,n) vis.set(i); tot=0; rep0(i,n) if (vis.ask(i)) dfs0(i); rep0(i,n) vis.set(i); int ans=0; dow(i,1,n) if (vis.ask(p[i])) { tot=0; dfs1(p[i]); ans+=tot*(tot-1)/2; } return ans; } int main() { int tt; scanf("%d",&tt); while (tt--) { scanf("%d %d",&n,&m); rep0(i,n) { g[i].reset(); rg[i].reset(); } rep0(i,n) { scanf("%s",s); rep0(j,n) if (s[j]=='1') add(i,j); } while (m--) { scanf("%d",&kk); while (kk--) { int j,k; scanf("%d %d",&j,&k); add(j-1,k-1); } printf("%d ",calc()); } } return 0; }
另外是一個總結
Bitset 头文件：#include<bitset> bitset<32> bits; b.any() b中是否存在置为1的二进制位？ b.none() b中不存在置为1的二进制位吗？ b.count() b中置为1的二进制位的个数 b.size() b中二进制位数的个数 b[pos] 访问b中在pos处二进制位 b.test(pos) b中在pos处的二进制位置为1么？ b.set() 把b中所有二进制位都置为1 b.set(pos) 把b中在pos处的二进制位置为1 b.reset( ) 把b中所有二进制位都置为0 b.reset( pos ) 把b中在pos处的二进制位置置为0 b.flip( ) 把b中所有二进制位逐位取反 b.flip( pos ) 把b中在pos处的二进制位取反 b.to_ulong( ) 把b中同样的二进制位返回一个unsigned int __builtin_ffs (unsigned x) 返回x中最后一个1是从右往左第几位 int __builtin_popcount (unsigned x) 返回x中1的个数 int __builtin_ctz (unsigned x) 返回x末尾0的个数(x等于0时未定义) int __builtin_clz (unsigned x) 返回x中前导0的个数(x等于0时未定义) int __builtin_parity (unsigned x) 返回x中1的奇偶性