Gym - 100342J：Triatrip(Bitset加速求三元环的数量)

题意：求有向图里面有多少个三元环。

思路：枚举起点A，遍历A可以到的B，然后求C的数量，C的数量位B可以到是地方X集合，和可以到A的地方Y集合的交集（X&Y）。

B点可以枚举，也可以遍历。（两种都试过，区别不大。）

枚举代码：

#include<cstdio>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

bitset<maxn>s[maxn];

bitset<maxn>f[maxn];

char c[maxn]; long long ans;

int main()

{

    freopen("triatrip.in","r",stdin);//必须加上，不然得WA

    freopen("triatrip.out","w",stdout);

    int N,i,j;

    scanf("%d",&N);

    for(i=;i<=N;i++){

       scanf("%s",c+);

       for(j=;j<=N;j++){

         if(c[j]=='+'){

           s[i].set(j);

           f[j].set(i);

         }

       }

    }

    for(i=;i<=N;i++)

        for(j=;j<=N;j++)

          if(s[i][j])

              ans+=(s[j]&f[i]).count();

    printf("%lld\n",ans/);

    return ;

}

遍历代码：

#include<cstdio>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

bitset<maxn>s[maxn];

bitset<maxn>f[maxn];

const int maxm=; char c[maxn];

int Laxt[maxn],Next[maxm],To[maxm],cnt;

long long ans;

void update(int N)

{

    for(int i=;i<=N;i++) s[i].reset();

    for(int i=;i<=N;i++) f[i].reset();

    memset(Laxt,,sizeof(Laxt));

    cnt=ans=;

}

void add(int u,int v)

{

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

}

int main()

{

    freopen("triatrip.in","r",stdin);//必须加上，不然得WA

    freopen("triatrip.out","w",stdout);

    int N,i,j;

    while(~scanf("%d",&N)){

        update(N);

        for(i=;i<=N;i++){

           scanf("%s",c+);

           for(j=;j<=N;j++){

                  if(c[j]=='+'){

                         add(i,j);

                         s[i].set(j);

                         f[j].set(i);

                  }

           }

        }

        for(i=;i<=N;i++){

            for(j=Laxt[i];j;j=Next[j]){

                int u=To[j];

                ans+=(s[u]&f[i]).count();

            }

        }

        printf("%lld\n",ans/);

    }

    return ;

}