<>

题目大意：

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

解题分析：

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

#include 
     
      using namespace std;const int N = 1500+5;bitset
      
       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