“玲珑杯”ACM比赛 Round #24: C. この戦いが終わったら（BFS+bitset优化暴力）-白红宇

“玲珑杯”ACM比赛 Round #24: C. この戦いが終わったら（BFS+bitset优化暴力）

阅读量：2143 次

发布时间：2019-04-30

本文共 1479 字，大约阅读时间需要 4 分钟。

给你一个无向图，每次查询的时候给一堆二元组(xi,yi)
 求图中有多少个点u与至少一个这次询问给出的二元组(xi,yi)满足dist(u,xi)<=yi，dist表示这两个点在图中的距离
 如果不连通dist = inf

INPUT

      第一行三个数表示n，m，qn表示顶点个数，m表示边数之后m行每行两个数x，y表示这两个点之间连有一条边~，边权都为1之后q次询问，每个询问先给你一个数a之后a行每行两个数，x，y，表示一个二元组n <= 1000 , m <= 100000 , q <= 100000a的和 <= 2100000 

OUTPUT

      q行，每行一个数表示这次询问的答案 

SAMPLE INPUT

       5 6 6 

       2 3 1 3 2 5 1 3 3 2 2 5 

1

3 1

1

1 1

1

1 4

1

5 2

1

1 4

2

       1 0 5 1 

SAMPLE OUTPUT

3

2

4

3

4

3

先n*m预处理每个点到所有点的最短路，然后开个bitset

p[x][y]是个长度为n的01串，表示从x点出发距离小于等于y的到达情况

比如n=8，p[2][3] = 01110010，意思就是从第2个点出发距离小于等于3的点有4个，分别是2、3、4、7号点

即为1表示能到，为0表示到不了

之后查询对于每个二元组(x, y)，只要将对应的p[x][y]或起来，最后答案就是串里面1的个数

复杂度O(n*m+n*a/32)

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;bitset<1005> B[1005][1005], ans;vector
         
           G[1005];typedef struct{ int x; int step;}Res;Res temp, now;queue
          
            Q;int vis[1005], road[1005][1005];int Read(){ int x = 0, f = 1; char ch; ch = getchar(); while(ch<'0' || ch>'9') { if(ch=='-') f = -1; ch = getchar(); } while(ch>='0' && ch<='9') x = x*10+ch-'0', ch = getchar(); return x*f;}int main(void){ int n, m, q, x, i, y, j; scanf("%d%d%d", &n, &m, &q); for(i=1;i<=m;i++) { x = Read(); y = Read(); if(road[x][y] || x==y) continue; road[x][y] = road[y][x] = 1; G[x].push_back(y); G[y].push_back(x); } for(i=1;i<=n;i++) { memset(vis, 0, sizeof(vis)); now.x = i, now.step = 0; Q.push(now); vis[now.x] = 1; while(Q.empty()==0) { now = Q.front(); B[i][now.step][now.x] = 1; Q.pop(); for(j=0;j