Gym 100342J Triatrip (求三元环的数量) (bitset优化)

<题目链接>

题目大意：
用用邻接矩阵表示一个有向图，现在让你求其中三元环的数量。

解题分析：
先预处理得到所有能够直接到达每个点的集合$arrive[N]$和所有能够由当前点到达的集合$to[N]$。然后就是枚举三元环中的两个点$a,b$，然后再求$arrive[a]$与$to[b]$的交集，因为三元环中每个点都计算了一遍它所在所有三元环的数量，所以最后的答案就是所有点的交集之和/3。同时，因为$n\leq1500$，所以这里用到了bitset优化常数。

#include <bits/stdc++.h>
using namespace std;

const int N = 1500+5;
bitset<N>arrive[N],to[N];

int main(){
    freopen("triatrip.in","r",stdin);
    freopen("triatrip.out","w",stdout);
    int n;scanf("%d",&n);
    char s[N];
    for(int i=1;i<=n;i++)arrive[i].reset(),to[i].reset();   
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=n;j++){
            if(s[j]=='+')arrive[j].set(i),to[i].set(j);  //能够到达j的点和能够从i点到达的点
        }
    }
    long long ans=0;
    for(int s=1;s<=n;s++)  //枚举三元环中的两个点
        for(int e=1;e<=n;e++){
            if(to[s][e])ans+=(arrive[s]&to[e]).count();
        }
    printf("%lld\n",ans/3);     
}

 

 

2019-03-07