传递

因为文化课复习实在捉急qwq，题解就一切从简了qwq

简单说一说

上来一看这道题没看出来突破点在哪。。。

去HDU上看原题，发现原题是带样例的图解的，然鹅还是没找到思路（太菜了吧）

没办法看了一手大佬的题解，发现都是一句话bitset。。。可是我这个蒟蒻不会用。。。还好有BFS版的挽救我脆弱的心灵

其实说到底就是这个传递的关系要搞明白。假如A是B的父亲，B是C的父亲，那么A必须也是C的父亲，这样才算是传递关系。也就是说，C既是A的孙子又是A的儿子（大雾）。

再假如，A有B、C、D三个儿子，如果B能指向C，那么ABC是满足传递关系的。可如果B指向了EFG等等一堆乱七八糟的，只要有一个不是A能指向的，那么图肯定是不合法的。

所以BFS之，两张图的N个点都遍历一遍，搜索时传一个nex变量（这里用结构体保存，跟点绑在一起），代表这个点的辈分（大雾），如果nex大于等于了2，说明他一定是某个点孙子辈的，但他还不是那个点的儿子，所以不合法直接判掉。

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

const int maxn=1e6+10;

const int inf=0x3f3f3f3f;

#define ll long long

struct Node{

    int num,nex;

    Node();

    Node(int a,int b){

        num = a,nex = b;

    }

};

vector<int> q[maxn];

vector<int> p[maxn];

char s[maxn];

int n;

int a[maxn];

bool vis[maxn];

bool Check(char flag){

    for(int i=1;i<=n;i++){

        memset(vis,0,sizeof vis);

        queue<Node> que;

        que.push(Node(i,0));

        while(!que.empty()){

            int num = que.front().num;

            int nex = que.front().nex;

            que.pop();

            if(nex >= 2) return 0;

            if(flag == 'P'){

                for(int i = 0;i < p[num].size();i++){

                    int v = p[num][i];

                    if(!vis[v]){

                        vis[v] = 1;

                        que.push(Node(v,nex+1));

                    }

                }

            }

            else if(flag == 'Q'){

                for(int i = 0;i < q[num].size();i++){

                    int v = q[num][i];

                    if(!vis[v]){

                        vis[v] = 1;

                        que.push(Node(v,nex+1));

                    }

                }

            }

        }

    }

    return 1;

}

int main(){

    int t;

    cin>>t;

    while(t){

        t--;

        scanf("%d",&n);

        for(int i = 1;i <= n;i++)

            q[i].clear(),p[i].clear();

        for(int i = 1;i <= n;i++){

            scanf("%s",s+1);

            for(int j = 1;j <= n;j++){

                if(s[j] == 'P') p[i].push_back(j);

                if(s[j] == 'Q') q[i].push_back(j);

            }

        }

        if(Check('P') && Check('Q'))

            printf("T\n");

        else

            printf("N\n");

    }

}

巴特西

HDU5961 传递

传递

简单说一说

最新文章

热门文章