【题解】Luogu P5068 [Ynoi2015]我回来了

时间：2022-05-25 14:38:24

众所周知lxl是个毒瘤，Ynoi道道都是神仙题，这道题极其良心，题面好评

原题传送门

我们先珂以在\(O(n^2)\)的时间内bfs求出任意两点距离

我们考虑如何计算从一个点到所有点的最短路长度小于等于k的点的数量

我们先求出来从一个点到所有点的最短路长度等于k的点的数量，这个珂以在bfs搜索过程中完成

统计最短路长度小于等于k的点的数量珂以使用前缀和

这里明显不好直接前缀和，我们可以使用bitset来维护一个点到所有点的最短路长度小于等于k的点的数量，如果一位是1，就代表满足条件，否则不满足条件

做前缀和时就直接用“|”就行了、

以上搜索和前缀和的复杂度为\(O(\frac {n^3}{\omega})\)（\(\omega\)是一个常数，这里珂以取32）

最后询问时开一个bitset，把所有条件的答案“|”起来，就是求出满足条件点的个数，最后输出这个bitset的count()，也就是1（满足）的个数

查询的复杂度为\(O(\frac {n \sum_{i=1}^{q} a_i}{\omega})\)

这道题存边不能用链式前向星，链式前向星会tle，因为地址不是连续的，所以用vector存边就行了qaq

总复杂度为\(O(\frac {n^3+n \sum_{i=1}^{q} a_i}{\omega})\)

#include <bits/stdc++.h>

#define N 1010

#define M 100010

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

vector <int> to[N];

int n,m,q;

int dis[N][N];

bitset <N> dissum[N][N];

inline void bfs(register int x,register int id)

{

    for(register int i=1;i<=n;++i)

        dis[id][i]=1005;

    queue <int> q;

    q.push(x);

    dis[id][x]=0;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(register int i=0;i<to[u].size();++i)

            if(dis[id][to[u][i]]==1005)

            {

                dis[id][to[u][i]]=dis[id][u]+1;

                q.push(to[u][i]);

            }

    }

    for(register int i=1;i<=n;++i)

        dissum[id][dis[id][i]].set(i);

    for(register int i=1;i<=n;++i)

        dissum[id][i]|=dissum[id][i-1];

}

int main()

{

    n=read(),m=read(),q=read();

    while(m--)

    {

        int u=read(),v=read();

        to[u].push_back(v),to[v].push_back(u);

    }

    for(register int i=1;i<=n;++i)

        bfs(i,i);

    while(q--)

    {

        bitset <N> ans;

        int x=read();

        while(x--)

        {

            int u=read(),k=read();

            ans|=dissum[u][k];

        }

        write(ans.count()),puts("");

    }

    return 0;

}

相关文章