题解：P10231 [COCI 2023/2024 #4] Putovanje

· · 题解

前言

身为一名蒟蒻，刚接触多源 BFS，前面众多大佬的题解看不懂，于是我决定写一篇入门一点的题解。

暴力

枚举所有点，当一个点 s 的 d_s 不为 -1 的时候，从它开始跑 BFS，找到所有到 s 距离为 d_s 的点并将它们标记一次。答案就是被所有 d 不为 -1 的点标记过的点。时间复杂度 O(n(n+m))。

暴力代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
long long n,m,d,b[maxn],cnt,ans;
bool bb[maxn];
vector<long long> a[maxn];
struct xxx
{
    long long u,w;
};
queue<xxx> f;
void bfs(int s)
{
    for(int i=1;i<=n;i++)
    bb[i]=0;
    f.push({s,0});
    bb[s]=1;
    while(!f.empty())
    {
        int u=f.front().u,w=f.front().w;
        f.pop();
        if(w==d)
        {
            b[u]++;
            continue;
        }
        for(int v:a[u])
        {
            if(bb[v]==1)
            continue;
            bb[v]=1;
            f.push({v,w+1});
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>d;
        if(d==-1)
        continue;
        bfs(i);
        cnt++;
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i]==cnt)
        ans++;
    }
    cout<<ans<<"\n";
    for(int i=1;i<=n;i++)
    {
        if(b[i]==cnt)
        cout<<i<<" ";
    }
}

正解

思路转化

我们将暴力思路转化一下。对于一个 d 不为 -1 的点 s，设其层数 h_s 为 d_s，与他相邻的点的层数为 h_s-1，以此类推，向周围扩散，每扩散一次层数减一。那么每次 BFS 所标记的点就是层数为 0 的点。

那是不是可以把所有起点放在一个 BFS 里一起跑呢？这就是多源 BFS。

多源 BFS

多源 BFS，顾名思义，就是有很多个起点的 BFS。我们知道，在跑上面暴力思路转化的普通 BFS 的时候，程序总是先把层数最大的起点向周围扩散，再扩散新入队的层数次大的点……它处理的点的层数序列一定是一点一点单调递减的。多源 BFS 也要满足这个性质。所以我们对于多个起点，先把层数最大的放进队列里，随着程序处理的层数一点一点降低，再把对应层数的起点加入队列。

判断合法

我们给每一个点都开一个 bitset，表示当前点的层数可以被多少起点所扩散到。答案即为所有层数为 0 并且其 bitset 中非零位的数量等于起点数量的点。

如何扩散

当我们由 u 扩散到相邻点 v 时，我们发现此时的 v 的层数只有三种情况：

  3. （1）它们是由同一个起点扩散而来的，那肯定不继续扩散。（2）它们是由不同起点扩散而来的，两个起点对 $v$ 的层数要求不一样，那么 $v$ 就肯定不会被计入答案，而且再以它扩散出的点对于这两个起点的层数肯定也不一样，所以它们也不会计入答案，故不继续扩散。 ### 时间复杂度 多源 BFS：$O(n+m)$。

bitset 合并：O(\frac{n}{w})，w 取 32。

总复杂度：O(\frac{n(n+m)}{w})。

正解代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
long long n,m,u,v,h[maxn],cnt,ans;
struct xxx
{
    int x,y;
    bool operator < (const xxx o) const {return x>o.x;}
    bool operator > (const xxx o) const {return x<o.x;}
}d[maxn];
vector<int> a[maxn];
bitset<maxn> b[maxn];
queue<int> f;
void bfs()
{
    memset(h,-1,sizeof(h));
    int z=1;
    for(;z<=n;z++)
    {
        h[d[z].y]=d[z].x;
        f.push(d[z].y);
        b[d[z].y].set(d[z].y);//myBitset.set(x)：将bitset的第x位设为1
        if(d[z+1].x!=d[z].x)
        break;
    }
    while(!f.empty())
    {
        int u=f.front();
        f.pop();
        for(;z<=n&&d[z].x==h[u];z++)
        {
            if(h[d[z].y]>d[z].x)
            continue;
            if(h[d[z].y]<0)
            {
                h[d[z].y]=d[z].x;
                f.push(d[z].y);
            }
            b[d[z].y].set(d[z].y);
        }
        if(h[u]==0)
        continue;
        for(int v:a[u])
        {
            if(h[v]<0||h[u]-1==h[v])
            {
                b[v]|=b[u];//bitset支持位运算
                if(h[v]<0)
                {
                    h[v]=h[u]-1;
                    f.push(v);
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>d[i].x;
        d[i].y=i;
        if(d[i].x!=-1)
        cnt++;
    }
    if(cnt==0)//注意要特判
    {
        cout<<n<<"\n";
        for(int i=1;i<=n;i++)
        cout<<i<<" ";
        return 0;
    }
    sort(d+1,d+n+1);
    bfs();
    for(int i=1;i<=n;i++)
    {
        if(h[i]==0&&b[i].count()==cnt)//myBitset.count(x)：计算bitset中1的个数
        ans++;
    }
    cout<<ans<<"\n";
    for(int i=1;i<=n;i++)
    {
        if(h[i]==0&&b[i].count()==cnt)
        cout<<i<<" ";
    }
}