【题解】[牛客网NOIP赛前集训营-提高组（第七场）]C.洞穴 倍增优化DP+bitset
#include<cstdio>
#include<bitset>
using namespace std;
const int N=110;
int n,m,q;
bitset<N>f[N][31];
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)
scanf("%d%d",&u,&v),f[u][0][v]=1;
for(int i=0;i<30;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(f[j][i][k])f[j][i+1]|=f[k][i];
scanf("%d",&q);
while(q--)
{
int l,u,v;scanf("%d%d%d",&l,&u,&v);
bitset<N>ans;ans[u]=1;
for(int i=0;i<31;i++)
if(l&(1<<i))
{
bitset<N>tmp;
for(int j=1;j<=n;j++)
if(ans[j])tmp|=f[j][i];
ans=tmp;
}
if(ans[v])puts("YES");
else puts("NO");
}
return 0;
}
总结
DP判断可行性，倍增优化好题