M_sea

洛谷5068 [Ynoi2015]我回来了
Luogu分析这大概是 $\mathrm{Ynoi}$ 中最简单的题了qwq$\mathrm{bitset}$ 。...
扫描右侧二维码阅读全文
05
2019/04

洛谷5068 [Ynoi2015]我回来了

Luogu

分析

这大概是 $\mathrm{Ynoi}$ 中最简单的题了qwq


$\mathrm{bitset}$ 。

设 $dis[i][j]$ 表示 $i$ 到 $j$ 的距离, $f[i][j]$ 表示到 $i$ 的距离为 $j$ 的点集。显然 $f$ 可以用 $\mathrm{bitset}$ 维护。

$dis$ 和 $f$ 都只用跑 $n$ 遍 $\mathrm{bfs}$ 即可求出。

现在考虑求出一个 $g[i][j]$ 表示到 $i$ 的距离 $\leq j$ 的点集。发现对 $f$ 做一遍前缀或就行了。

那么询问直接求出所有 $g[x][y]$ 的并,然后 $1$ 的数量就是答案。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;

int n,m,Q;
vector<int> G[N];
int dis[N][N];
bitset<N> f[N][N],ans;

inline void bfs(int s) {
    queue<int> Q; Q.push(s);
    dis[s][s]=0,f[s][0][s]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int i=0;i<G[u].size();++i) {
            int v=G[u][i];
            if (dis[s][u]+1<dis[s][v]) {
                dis[s][v]=dis[s][u]+1,f[s][dis[s][v]][v]=1;
                Q.push(v);
            }
        }
    }
    for (re int i=1;i<=n;++i) f[s][i]|=f[s][i-1];
}

int main() {
    n=read(),m=read(),Q=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
    }
    memset(dis,0x3f,sizeof(dis));
    for (re int i=1;i<=n;++i) bfs(i);
    while (Q--) {
        int T=read(); ans.reset();
        while (T--) {
            int x=read(),y=read();
            ans|=f[x][min(y,n)];
        }
        printf("%d\n",ans.count());
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 36 PM

发表评论