题解：P11591 [NordicOI 2024] Anime Shops

· · 题解

Solution

纯暴力思路。不知道为什么能过还跑得飞快。感觉可以被卡到 O(n^2)。可能是我不会算时间复杂度的问题吧 /yun。

为叙述方便，以下称有动漫商店的点为黑点，其它为白点。

我们可以对于 k 个黑点都进行一次 BFS，找到其它每个点与它的距离。一个很难注意不到的且很有效的剪枝是：对于每一个节点，若其当前的最近距离 dis_u 小于等于此次 BFS 当前的 step，那么我们不再让其入队。正确性显然。而且非常非常好写。

然而，我这么写，获得了零分的好成绩！

:::error[零分代码]

#include<bits/stdc++.h>
using namespace std;

int n,m,k,a[100005];
vector<int> e[100005];
struct node{
    int u,step;
};
queue<node> q;
int dis[100005];
int vis[100005];

void bfs(int st){
    while(!q.empty())
        q.pop();
    q.push({st,0});
    vis[st]=st;
    while(!q.empty()){
        int u=q.front().u,step=q.front().step;
        q.pop();
//      cout<<u<<" "<<dis[u]<<endl;
        for(auto v:e[u]){
            if(dis[v]<=step+1||vis[v]==st)
                continue;
            dis[v]=step+1;
            q.push({v,step+1});
            vis[v]=st;
        }
    }
    return;
}

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=k;i++)
        bfs(a[i]);
    for(int i=1;i<=n;i++)
        if(dis[i]==0x3f3f3f3f) cout<<-1<<" ";
        else cout<<dis[i]<<" ";
    return 0;   
}

:::

求助于全知全能聪慧过人的 @JACK0927 为什么我的暴力没有 TLE 但是 WA，于是他送了我一个 hack，大家快去膜拜他！

:::info[hack] hack.in

9 9 2
1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 1

hack.out

3 1 2 3 2 1 3 1 1

零分代码输出：

-1 1 2 3 2 1 3 1 1

:::

检查代码发现，这个算法不能很好地处理黑点。以上述 hack 为例：在以 1 号点为初始节点 BFS 时，1 号点自身没有被更新，dis_8=1。在以 7 号点为初始节点 BFS 时，当搜索到 8 号点，step=1，不小于 dis_8，于是不将 8 号点加入搜索队列，于是不能用 7 号点更新 1 号点，导致 1 号点答案未被记录。

考虑如何高效简便地解决这一问题。

我们在 BFS 时，用 fa_i 记下距离 i 最近的黑点。在以另一黑点 s 为起点 BFS 搜索到 i 时，尝试用 dis_i+step+1 更新 dis_{fa_i}，即用当前黑点 s 更新另一黑点 u。正确性也显然。

于是我们解决了这一问题。

:::success[Code]

#include<bits/stdc++.h>
using namespace std;

int n,m,k,a[100005],f[100005];
vector<int> e[100005];
struct node{
    int u,step;
};
queue<node> q;
int dis[100005],fa[100005];
int vis[100005];

void bfs(int st){
    while(!q.empty())
        q.pop();
    q.push({st,0});
    vis[st]=st;
    while(!q.empty()){
        int u=q.front().u,step=q.front().step;
        q.pop();
        for(auto v:e[u]){
            if(dis[v]!=0x3f3f3f3f&&fa[v]!=st)
                if(dis[v]+step+1<dis[fa[v]]){
                    dis[fa[v]]=dis[v]+step+1;
                    fa[fa[v]]=st;
                }

            if(dis[v]<=step+1||vis[v]==st)
                continue;
            dis[v]=step+1;
            fa[v]=st;
            q.push({v,step+1});
            vis[v]=st;
        }
    }
    return;
}

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
        cin>>a[i],f[a[i]]=1;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=k;i++)
        bfs(a[i]);
    for(int i=1;i<=n;i++)
        if(dis[i]==0x3f3f3f3f) cout<<-1<<" ";
        else cout<<dis[i]<<" ";
    return 0;   
}

:::