【hdu6072】Logical Chain

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[];

    void reset()  //clear

    {

        memset(v,,sizeof(v));

    }

    void set(int x) //set v[x]=1

    {

        v[x>>]|=1u<<(x&);

    }

    void flip(int x) // rev

    {

        v[x>>]^=1u<<(x&);

    }

    bool ask(int x)  // is == 1?

    {

        return v[x>>]>>(x&)&;

    }

}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 = ;

   if ((x >> ) == ) {n = n +; x = x <<;}

   if ((x >> ) == ) {n = n + ; x = x << ;}

   if ((x >> ) == ) {n = n + ; x = x << ;}

   if ((x >> ) == ) {n = n + ; x = x << ;}

   n = n - (x >> );

   return -n;

}

void dfs0(int x)

{

    vis.flip(x);

    rep0(i,) {

        unsigned int now=vis.v[i]&g[x].v[i];

        while (now) {

            dfs0(i<<|nlz(now));

            now=vis.v[i]&g[x].v[i];

        }

    }

    p[++tot]=x;

}

void dfs1(int x)

{

    vis.flip(x);

    ++tot;

    rep0(i,) {

        unsigned int now=vis.v[i]&rg[x].v[i];

        while (now) {

            dfs1(i<<|nlz(now));

            now=vis.v[i]&rg[x].v[i];

        }

    }

}

int calc()

{

    vis.reset();

    rep0(i,n) vis.set(i);

    tot=;

    rep0(i,n)

        if (vis.ask(i)) dfs0(i);

    rep0(i,n) vis.set(i);

    int ans=;

    dow(i,,n)

        if (vis.ask(p[i])) {

            tot=;

            dfs1(p[i]);

            ans+=tot*(tot-)/;

        }

    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]=='') add(i,j);

        }

        while (m--) {

            scanf("%d",&kk);

            while (kk--) {

                int j,k;

                scanf("%d %d",&j,&k);

                add(j-,k-);

            }

            printf("%d\n",calc());

        }

    }

    return ;

}

另外是一個總結

Bitset

头文件：#include<bitset>

bitset<> 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的奇偶性