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

· · 题解

Putovanje

暴力

就这道题来说，暴力解法无疑是我们需要从每个点开搜一遍，然后通过判断 dis 合不合法来判断该点为起点合不合法。

思路

正解的思路其实就是对暴力代码的优化。什么意思呢？我们改变我们 BFS 方式，多源 BFS。

根据 u 到 v 的最短路距离等于 v 到 u 的最短路距离，这个时候我们将从起点开搜的过程反过来，当成搜索起点，走一步此时看作距离 -1。

因为此时是逆序找源点的过程，我们可能存在一个点在没法从 dis 更大的点转移到这个点，那么我们加源点的时候通过 dis 从大到小来满足在搜索时每一层的距离都是相同的，就是处于相同的 BFS 层。并把处于这一层上面那一层的点加入。如果已经有一个点被搜索过了，那么他就不必再加入队列。

并且我们要判断一下 dis_{y} 是否等于 d_{y}，如果不等，说明此时的局面不合法，那么无解。局面不合法怎么理解？

如果当前我们在将上一层的点加入时，如果已经有一个搜过了。那么，如果此时的距离 d_{x}>dis_{x}，说明，那些 dis 大的点原本是应该有更小的最短路径的，所以此时的局面出现了冲突，那么整个局面都不合法了。

此时，因外上述加点过程严格保证了层与层之间的关系，所以我们能够保证每一个点只会进入队列一次。

我们用一个 bitset 来储存哪些点能到达这个点，如果到达这个点的个数为最开始拥有 dis 不为 -1 的点的个数，并且，这个点最终 d_{i}=0 那么这个点就可以为源点。

如果光看 BFS 的时间复杂度的话，那么时间复杂度仅为 O(n+m)。但是，我们使用的 bitset 数据结构，逻辑或的时间复杂度为 \frac{N}{w}。在每次向外扩张的过程中，我们会用到 bitset，那么时间复杂度的主要瓶颈就为 \frac{n\times m}{w}，w 为 bitset 自带的常数，因为我们相当于是把一个 bool 的每一位空间从 1 字节 减少到了 1 比特。一个整形 4 个字节，那么 w 就大约为 32。

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 5e4+10;

typedef long long ll;
typedef pair<int,int> pii;

int n,m,d[N],dis[N],uk;

bool flag=true;

bool vis[N];
vector<int> e[N];
vector<int> v[N];
queue<int> q;
bitset<N> s[N];

void add(int u,int v){
    e[u].push_back(v);
}//end

void bfs(){
    while (q.size()) {
        int now=q.front();
        q.pop();

        if(!d[now]) continue;

        while(v[d[now]-1].size()) {
            int x=v[d[now]-1].back();
            v[d[now]-1].pop_back();

            if(vis[x]){
                if(dis[x]!=d[x]) flag=0;
                continue;
            }
            vis[x]=1;
            d[x]=dis[x];
            q.push(x);
            s[x].set(x);
        }
        for (int x:e[now]) {
            if (d[x]<d[now]) {
                d[x]=d[now]-1;
                s[x]|=s[now];
                if (!vis[x]) q.push(x);
                vis[x]=1;
            }
        }
    }
}//end

int main(){

//  freopen("putovanje.in","r",stdin);
//  freopen("putovanje.out","w",stdout);

    ios::sync_with_stdio(0);

    cin>>n>>m;

    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        add(u,v); add(v,u);
    }

    for(int i=1;i<=n;i++){
        cin>>dis[i];
        if(dis[i]!=-1){
            v[dis[i]].push_back(i);
            uk++;
        }
    }

    int j=n-1;
    while(j>=0&&v[j].empty()) j--;
    if(j==-1){
        cout<<n<<endl;
        for(int i=1;i<=n;i++) cout<<i<<" ";
        cout<<endl;
        return 0;   
    }

    for(int x:v[j]){
        vis[x]=1;
        d[x]=j;
        s[x].set(x);
        q.push(x);  
    }

    bfs();
    vector<int> ans;

    for(int i=1;i<=n;i++){
        if(flag&&d[i]==0&&s[i].count()==uk) ans.push_back(i);   
    }

    cout<<ans.size()<<endl;
    for(int x:ans) cout<<x<<" ";
    cout<<endl;

    return 0;
}//end