牛客挑战赛47 C.条件

传送门

一定存在的边放一起跑一边弗洛伊德

然后再加上可能存在的边跑弗洛伊德

这样是 $O(n^3)$ 的

但是由于这里只需要判断是否连通,所以可以使用或运算、

也就是把每个点能到的点看成一个二进制数,这样可以使用 $bitset$ 优化复杂度

一定存在的边放一起跑一边弗洛伊德

然后再加上可能存在的边跑弗洛伊德

这样是 $O(n^3)$ 的

但是由于这里只需要判断是否连通,所以可以使用或运算、

也就是把每个点能到的点看成一个二进制数,这样可以使用 $bitset$ 优化复杂度

一定存在的边放一起跑一边弗洛伊德

然后再加上可能存在的边跑弗洛伊德

这样是 $O(n^3)$ 的

但是由于这里只需要判断是否连通,所以可以使用或运算、

也就是把每个点能到的点看成一个二进制数,这样可以使用 $bitset$ 优化复杂度

#include <bits/stdc++.h>
using namespace std;
int n,m1,m2,q;
bitset<1001>bit1[1001],bit2[1001];
int main()
{
    cin >> n >> m1 >> m2 >>  q;
    for(int i=1;i<=n;i++) 
    for(int j=1;j<=n;j++)
    {
        bit2[i][j]=1;
        if( i==j )    bit1[i][j] = 1;
    }
    for(int i=1;i<=m1;i++)
    {
        int x,y; cin >> x >> y;
        bit1[x][y] = 1;    
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    {
        //正常来说枚举一个j,然后dis[i][j] |= dis[i][k]&&dis[k][j] 
        if( bit1[i][k]==0 )    continue;
        bit1[i] |= bit1[k];
    }
    for(int i=1;i<=m2;i++)
    {
        int x,y; cin >> x >> y; bit2[x][y] = 0;
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    {
        //正常来说枚举一个j,然后dis[i][j] |= dis[i][k]&&dis[k][j] 
        if( bit2[i][k]==0 )    continue;
        bit2[i] |= bit2[k];
    }
    while( q-- )
    {
        int x,y; cin >> x >> y;
        if( bit1[x][y] )    cout << "Yes ";
        else    cout << "No ";
        if( bit2[x][y] )    cout << "Yes\n";
        else    cout << "No\n";
    }
}