题目描述
有一天，牛牛找到了一个巨大的洞穴。洞穴可以描述成一个有向图，一共有(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 li 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)
输出描述:
输出(Q)行依次回答牛牛的(Q)个询问
每行输出YES或NO，YES代表存在符合条件的路径，NO代表不存在
示例1
输入
3 3
1 2
2 3
3 1
3
100 1 1
100 1 2
100 1 3
输出
NO
YES
NO
说明
这个图是一个三元环，从(1)号点开始走(100)步之后必定停在(2)号点上
Solution
嗯，先说50分的暴力分，显然就是一个裸的记忆化搜索结束。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
#define REP(i,a,n) for(register int i=(a);i<=(n);++i)
#define PER(i,a,n) for(register int i=(a);i>=(n);--i)
#define FEC(i,x) for(register int i=head[x];i;i=g[i].ne)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
namespace io{
const int SIZE=(1<<21)+1;char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
inline void putc(char x){*oS++=x;if(oS==oT)flush();}
template<class I>inline void read(I &x){for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;}
template<class I>inline void write(I x){if(!x)putc('0');if(x<0)putc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)putc(qu[qr--]);}
inline void print(const char *s){while(*s!=' ')putc(*s++);}
inline void scan(char *s){for(c=gc();c<=' ';c=gc());for(;c>' ';c=gc())*(s++)=c;*s=' ';}
struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}//orz laofudasuan
using io::read;using io::putc;using io::write;using io::print;
typedef long long ll;typedef unsigned long long ull;
template<typename A,typename B>inline bool SMAX(A&x,const B&y){return x<y?x=y,1:0;}
template<typename A,typename B>inline bool SMIN(A&x,const B&y){return y<x?x=y,1:0;}
const int N=100+7,M=100000+7;
int n,m,Q,x,y,z;char vis[N][N][N],dp[N][N][N];
struct Edge{int to,ne;}g[M];int head[N],tot;
inline void Addedge(int x,int y){g[++tot].to=y;g[tot].ne=head[x];head[x]=tot;}
inline char DFS(int x,int y,int z){
if(vis[x][y][z])return dp[x][y][z];if(x==y&&z==0)return dp[x][y][z]=vis[x][y][z]=1;
if(x!=y&&z==0)return vis[x][y][z]=1,dp[x][y][z]=0;
char &ans=dp[x][y][z];vis[x][y][z]=1;
for(register int i=head[x];i;i=g[i].ne)if(ans=(ans||DFS(g[i].to,y,z-1)))return ans=1;
return ans;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);freopen("C.out","w",stdout);
#endif
read(n),read(m);
for(register int i=1;i<=m;++i)read(x),read(y),Addedge(x,y);
read(Q);for(register int i=1;i<=Q;++i){
read(z),read(x),read(y);
io::print(DFS(x,y,z)?"YES
":"NO
");
}
}
然后考场上，我想了一会儿，感觉(10^9)的范围简直就是倍增的暗示，于是立刻1分钟敲了一个(O(n^3log n))的东西预处理出(f[i][j][k])表示从(i)到(j)花了(2^k)步是否可行。
然后就想了两个小时怎么处理询问，然候这个叫hkk的傻逼愣是没想到bitset这种东西。
我们定义一个bitset类型的数组(f[i][j])存下从(i)出发，走了(2^j)步可以到达的点。
于是(O(frac{n^3log n}{32}))预处理出(f)数组。
然后查询的时候倍增跳长度，每一次跳的时候再用bitset压一下从(x)跳目前倍增到的长度可以到达那些店，随便搞搞就行了。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<bitset>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
#define REP(i,a,n) for(register int i=(a);i<=(n);++i)
#define PER(i,a,n) for(register int i=(a);i>=(n);--i)
#define FEC(i,x) for(register int i=head[x];i;i=g[i].ne)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
namespace io{
const int SIZE=(1<<21)+1;char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
inline void putc(char x){*oS++=x;if(oS==oT)flush();}
template<class I>inline void read(I &x){for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;}
template<class I>inline void write(I x){if(!x)putc('0');if(x<0)putc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)putc(qu[qr--]);}
inline void print(const char *s){while(*s!=' ')putc(*s++);}
inline void scan(char *s){for(c=gc();c<=' ';c=gc());for(;c>' ';c=gc())*(s++)=c;*s=' ';}
struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}//orz laofudasuan
using io::read;using io::putc;using io::write;using io::print;
typedef long long ll;typedef unsigned long long ull;
template<typename A,typename B>inline bool SMAX(A&x,const B&y){return x<y?x=y,1:0;}
template<typename A,typename B>inline bool SMIN(A&x,const B&y){return y<x?x=y,1:0;}
const int N=100+7,M=100000+7,LOG=31;
int n,m,Q,x,y,z;bitset<N>f[N][LOG],pre,now;
struct Edge{int to,ne;}g[M];int head[N],tot;
inline void Addedge(int x,int y){g[++tot].to=y;g[tot].ne=head[x];head[x]=tot;}
inline void Preprocess(){
for(register int k=1;k<LOG;++k)
for(register int i=1;i<=n;++i)
for(register int j=1;j<=n;++j)if(f[i][k-1].test(j))
f[i][k]|=f[j][k-1];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);freopen("C.out","w",stdout);
#endif
read(n),read(m);
for(register int i=1;i<=m;++i)read(x),read(y),f[x][0].set(y);
Preprocess();read(Q);
for(register int i=1;i<=Q;++i){
read(z);read(x),read(y);now.reset();now.set(x);
for(register int k=LOG-1;k>=0;--k)if((1<<k)&z){
pre=now,now.reset();
for(register int j=1;j<=n;++j)if(pre.test(j))now|=f[j][k];
}
print(now.test(y)?"YES
":"NO
");
}
}