条件 题解(bitset优化floyd)

题目链接

题目思路

思路其实很简单就是跑两次floyd

但是问题是这样会超时，所以用bitset优化

bitset每位只占一个bit

而bool占一个byte

1byte=4bit

遍历bitset的复杂度为\(O({n}/{w})\)

w在根据计算机不同为32/64

具体的操作可以参考博客链接

这样复杂度优化到\(O(n^3/w)\)

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e3+5,inf=0x3f3f3f3f;
const int eps=1e-3;
const ll mod=1004535809;
bitset<maxn> a[maxn],b[maxn];
int n,m1,m2,q;
signed main(){
    scanf("%d%d%d%d",&n,&m1,&m2,&q);
    for(int i=1,u,v;i<=m1;i++){
        scanf("%d%d",&u,&v);
        a[u][v]=1;
    }
    for(int i=1,u,v;i<=m2;i++){
        scanf("%d%d",&u,&v);
        b[u][v]=1;
    }
    for(int i=1;i<=n;i++){
        b[i].flip();
    }
    for(int i=1;i<=n;i++){ //自己一定可以到达自己
        a[i][i]=b[i][i]=1;
    }
    for(int mid=1;mid<=n;mid++){
        for(int beg=1;beg<=n;beg++){
            if(a[beg][mid]){
                a[beg]|=a[mid];
            }
            if(b[beg][mid]){
                b[beg]|=b[mid];
            }
        }
    }
    for(int i=1,u,v;i<=q;i++){
        scanf("%d%d",&u,&v);
        if(a[u][v]){
            printf("Yes ");
        }else{
            printf("No ");
        }
        if(b[u][v]){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}