传递 HDU - 5961 题解

分析

题目大意：给一个竞赛图，将图分成两部分，判断两部分的图是否符合传递闭包，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[i][j]) p[i]|=p[j];

                if(q[i][j]) q[i]|=q[j];

            }

        }

        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实现。

巴特西

传递 HDU - 5961 题解

分析

代码

最新文章

热门文章