分析
题目大意：给一个竞赛图，将图分成两部分，判断两部分的图是否符合传递闭包，a->b，b->c，则a->c
这道题用Floyd硬跑的显然n\({^3}\)会T
如果用bfs可能能过，不过有些麻烦，而且时限也不少
其实传递闭包的话用bitset就可以了
时间效率为n\({^2}\)，一共有20组数据，所以实际还要大一些
但是bitset的常数非常小，大概只有\(\frac{1}{32}\),所以过这一道题还是没有问题的
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2021;
bitset<maxn> p[maxn];
bitset<maxn> q[maxn];
bool visq[maxn][maxn],visp[maxn][maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
for(int i=0;i<maxn;i++){
p[i].reset();
q[i].reset();
}
memset(visq,0,sizeof(visq));
memset(visp,0,sizeof(visp));
int n;
scanf("%d",&n);
char ch;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf(" %c",&ch);
if(ch=='P') p[i][j]=1,visp[i][j]=1;
if(ch=='Q') q[i][j]=1,visq[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(p[j][i]) p[j]|=p[i];
if(q[j][i]) q[j]|=q[i];
}
}
bool jud=0;
for(int i=1;i<=n;i++){
if(jud) break;
for(int j=1;j<=n;j++){
if(visp[i][j]==0 && p[i][j]==1) jud=1;
if(visq[i][j]==0 && q[i][j]==1) jud=1;
}
}
if(jud) printf("N\n");
else printf("T\n");
}
return 0;
}
下面附上正解思路：竞赛图即为任意两点中间有且只有一条有向边。一开始想暴力解决然后T了，最后看题解知道应该存两个图，其中Q的反向边存在P里，P的反向边存在Q里，然后在两个图内判断是否有环即可，有环则代表不传递。判断有环可用dfs实现。