【牛客网 NOIP 2018 赛前集训营 第七场】洞穴 / 题解

题目描述

有一天,牛牛找到了一个巨大的洞穴。洞穴可以描述成一个有向图,一共有 $N$ 个节点(从 $1$ 到 $N$ 编号)和 $M$ 条长度为 $1$ 的有向边,每条边从某一个节点 $u$ 连向另一个节点 $v$($u$ 可能等于 $v$)。

为了更好的探索洞穴,牛牛向你提出了 $Q$ 个问题,每个问题给定两个节点 $a, \ b$ 以及一个数 $l$, 你需要告诉牛牛是否存在一条开始于 $a$,结束于 $b$ 的路径,总长度为 $l$。(路径中可以经过任意点、边多次,但只能沿着单向边给定的方向行走,不允许反向行走)。

输入输出

第一行两个数 $N, \ M$ 代表点数和边数
接下来 $M$ 行每行两个整数 $ u_i,\ v_i$ 代表第 $i$ 条边从 $u_i$ 连向 $v_i$,长度为 $1$
接下来一个整数 $Q$ 代表牛牛的问题数
接下来 $Q$ 行每行三个整数 $l_i,\ a_i,\ b_i$ 代表牛牛的一个询问

$20\%$的数据, $1 \leq M \leq 30,\ 1 \leq l_i \leq 5$
$50\%$的数据, $1 \leq li \leq 100$
$100\%$的数据, $1 \leq N \leq 100,\ 1 \leq M \leq 10000,\ 1 \leq Q \leq 1000,\ 1 \leq l_i \leq 10^9 ,\ 1 \leq a_i, b_i, u_i, v_i \leq N$

思路

一开始,没看清楚数据范围的我心态崩了。

看到数据范围后,想到使用倍增和 $bitset$,维护从一个点出发能达到的点数。那就。。。基本等同于暴力了。

代码

#include <bits/stdc++.h>
#define maxn 101
std::bitset<maxn>p[maxn][32];
std::bitset<maxn>now,next;
int n,m,q;
int main(){
    scanf("%d%d",&n,&m);
    for (register int i=1,a,b;i<=m;++i)
        scanf("%d%d",&a,&b),p[a][0][b]=1;
    for (register int k=1;k<32;++k)
        for (register int i=1;i<=n;++i)
            for (register int j=1;j<=n;++j)
                if (p[i][k-1][j]) p[i][k]|=p[j][k-1];
    scanf("%d",&q);
    for (register int i=1,l,x,y;i<=q;++i){
        scanf("%d%d%d",&l,&x,&y);
        now.reset();now[x]=1;
        for (register int j=31;~j;--j){
            if (!(l&(1<<j))) continue;
            next.reset();
            for (register int i=1;i<=n;++i)
                if (now[i]) next|=p[i][j];
            now=next;
        }
        puts(now[y]?"YES":"NO");
    }
}
Show Comments