[牛客挑战赛47]C.条件 （bitset加速floyd）

传送门

题意：

给定$n$个点的图，有$m_1$条边一定存在，有$m_2$条边一定不存在。
给出$Q$次询问，每次询问两个点$x$和$y$，问：

• $x$是否一定可达$y$
• $x$是否可能可达$y$

$(n\le 1000,Q\le 200000)$

做法：

首先要明确的思路是建两张图，一张是只有一定存在的边的，一张是包括一定存在的边和可能存在的边的。
然后对于两张图都预处理出点间的可达性，最后询问直接查询。

一种想法是有向图的可达性，我们用$SCC$求出强连通分量，然后缩点变成$DAG$，然后就可以搞了。

不过题解给的思路好像更妙一些。
有向图我们可以用$floyd$在$o(n^3)$下处理出两两可达性，然后用$bitset$加速一下，最终复杂度为$o(n^3/w)$,$w$为64。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bitset<1001>f[1001],f1[1001];
int mpp[1005][1005];
int main()
{
    
    int n,m1,m2,q;
    scanf("%d%d%d%d",&n,&m1,&m2,&q);
    for(int i=1;i<=m1;i++)
    {
    
        int a,b;
        scanf("%d%d",&a,&b);
        mpp[a][b]=1;
    }
    for(int i=1;i<=m2;i++)
    {
    
        int a,b;
        scanf("%d%d",&a,&b);
        mpp[a][b]=2;
    }
    for(int i=1;i<=n;i++)
    {
    
        for(int j=1;j<=n;j++)
        {
    
            if(i==j)f[i][j]=f1[i][j]=1;
            if(mpp[i][j]==1)
            {
    
                f[i][j]=1;
                f1[i][j]=1;
            }
            else if(mpp[i][j]==0)
            {
    
                f1[i][j]=1;
            }
        }
    }
    for(int k=1;k<=n;k++)
    {
    
        for(int i=1;i<=n;i++)if(f[i][k])
        {
    
            f[i]=f[i]|f[k];
        }
    }
    for(int k=1;k<=n;k++)
    {
    
        for(int i=1;i<=n;i++)if(f1[i][k])
        {
    
            f1[i]=f1[i]|f1[k];
        }
    }
    while(q--)
    {
    
        int a,b;
        scanf("%d%d",&a,&b);
        if(f[a][b])printf("Yes ");
        else printf("No ");
        if(f1[a][b])printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}