「Ynoi 2015」我回来了

发表于 | | 阅读次数:
字数统计: 477 字

Description

题目链接：Luogu 5068

珂朵莉给你一个 $n$ 个点，$m$ 条边的无向无权图，一共有 $q$ 次询问，每次询问的时候给一堆二元组 $(x_i,y_i)$ 求图中有多少个点 $u$ 与这次询问中至少一个二元组 $(x_i,y_i)$ 满足 $\text{dist}(u,x_i)\le y_i$，$\text{dist}$ 表示这两个点在图中的距离。如果不连通 $\text{dist}=\infin$。

数据范围：$1\le n\le 10^3$，$1\le m,q\le 10^5$，记二元组的个数和为 $a$ 则 $1\le a\le 2.1\times 10^6$

Solution

我们对每个点 $i​$ 和距离 $j​$ 维护一个 $\text{bitset}\ f_{i,j}​$ 表示和点 $i​$ 距离不超过 $j​$ 的点的集合。这个不超过可以用 $\text{bitset}​$ 的前缀或得到。

询问时只需要把 $f_{x_i,y_i}$ 这些 $\text{bitset}$ 或起来，点集的大小就是答案。

时间复杂度：$O(nm+\frac{n^3+an}{\omega})$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <bitset>
#include <queue>

const int N=1e3+5;
int n,m,q,dis[N];
bool vis[N];
std::vector<int> e[N];
std::bitset<N> f[N][N];

void bfs(int s) {
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    std::queue<int> q;
    q.push(s),dis[s]=0,vis[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int v:e[u]) {
            if(!vis[v]) dis[v]=dis[u]+1,vis[v]=1,q.push(v);
        }
    }
}
void init() {
    for(int i=1;i<=n;++i) {
        bfs(i);
        for(int j=1;j<=n;++j) {
            if(dis[j]!=0x3f3f3f3f) f[i][dis[j]][j]=1;
        }
        for(int j=1;j<=n;++j) f[i][j]|=f[i][j-1];
    }
}
int main() {
    scanf("%d%d%d",&n,&m,&q);
    while(m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v),e[v].push_back(u);
    }
    init();
    while(q--) {
        int p;
        std::bitset<N> ans;
        for(scanf("%d",&p);p--;) {
            int x,y;
            scanf("%d%d",&x,&y);
            ans|=f[x][y>n?n:y];
        }
        printf("%d\n",(int)ans.count());
    }
    return 0;
}
0%