更好的阅读体验

思路

考虑从每一个 $d_i \neq -1$ 的点开始往外走 $d_i$ 步，然后所有这些点走到的点的集合取交集就是答案，复杂度是 $\Theta(n^2)$ 的。

注意到我们需要对一些集合取交，容易想到 bitset 优化，此时的复杂度瓶颈在于 BFS 的次数。

因为 $u \leadsto v$ 的最短路等于 $v \leadsto u$ 的最短路，考虑将原先的起点看作终点，从原先的起点倒着走走到原来的终点，每一步距离为 $-1$。

可以直接上多源 Dijkstra，判断每一个 $d_u \neq -1$ 是否和跑出来的 $dis_u$ 相同即可。因为边权全部为 $-1$ 可以把 Dijkstra 换成 BFS，实现上当队顶的 $dis_u > d_x$ 时将 $x$ 丢到队列里面即可。

最后复杂度是 $\Theta(\frac{nm}{\omega})$。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 5e4 + 10,M = 2e5 + 10;
int n,m,tot,now;
int d[N],dis[N];
int idx,h[N],ne[M],e[M];
bitset<N> tmp,st[N];
vector<int> ans,S[N];

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

inline void add(int a,int b){
    ne[idx] = h[a];
    e[idx] = b;
    h[a] = idx++;
}

inline void bfs(){
    queue<int> q;
    fill(dis,dis + n + 3,-1);
    while (!q.empty() || ~now){
        if (q.empty()){
            while (~now && S[now].empty()) now--;
            if (~now){
                for (int x:S[now]){
                    q.push(x); dis[x] = d[x];
                } S[now--].clear();
            }
        }
        else if (dis[q.front()] == now){
            for (int x:S[now]){
                q.push(x); dis[x] = d[x];
            } S[now--].clear();
        }
        if (q.empty()) break;
        int u = q.front(); q.pop();
        if (~d[u] && d[u] != dis[u]){
            puts("0"); exit(0);
        }
        if (!dis[u]) continue;
        for (re int i = h[u];~i;i = ne[i]){
            int v = e[i];
            if (!~dis[v] || dis[v] == dis[u] - 1){
                if (!~dis[v]) q.push(v);
                st[v] |= st[u]; dis[v] = dis[u] - 1;
            }
        }
    }
}

int main(){
    memset(h,-1,sizeof(h));
    n = now = read(),m = read();
    for (re int i = 1,a,b;i <= m;i++){
        a = read(),b = read();
        add(a,b); add(b,a);
    }
    for (re int i = 1;i <= n;i++){
        tot += ~(d[i] = read());
        st[i][i] = 1;
        if (~d[i]){
            tmp[i] = 1; S[d[i]].push_back(i);
        }
    } bfs();
    for (re int i = 1;i <= n;i++){
        if ((!dis[i] || !~dis[i]) && (st[i] & tmp) == tmp) ans.push_back(i);
    } printf("%d\n",ans.size());
    for (int x:ans) printf("%d ",x);
    return 0;
}

有点看不懂题解，简单规整了一下代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
vector<int>G[N],G2[N];
bitset<N>tmp,st[N];
int d[N],dis[N],cnt,n,m;
void bfs()
{
	deque<int>q;memset(dis,-1,sizeof(dis));
	while(!q.empty()||cnt!=-1)
	{
		if(q.empty())
		{
			while(cnt!=-1&&G2[cnt].empty())cnt--;
			if(cnt!=-1)
			{
				for(int x:G2[cnt])q.push_back(x),dis[x]=d[x];
				G2[cnt].clear();cnt--;
			}
		}
		else if(dis[q.front()]==cnt)
		{
			for(int x:G2[cnt])q.push_back(x),dis[x]=d[x];
			G2[cnt].clear();cnt--;
		}
		if(q.empty())break;
		int x=q.front();q.pop_front();
		if(d[x]!=-1&&dis[x]!=d[x])
		{
			cout<<0<<'\n';
			exit(0);
		}
		if(!dis[x])continue;
		for(int y:G[x])if(dis[y]==-1||dis[y]==dis[x]-1)
		{
			if(dis[y]==-1)q.push_back(y);
			st[y]|=st[x],dis[y]=dis[x]-1;
		}
	}
}
signed main()
{
	cin>>n>>m;cnt=n;
	for(int i=1;i<=m;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>d[i];st[i][i]=1;
		if(d[i]!=-1)tmp[i]=1,G2[d[i]].push_back(i);
	}
	bfs();
	vector<int>ans;
	for(int i=1;i<=n;i++)if((dis[i]==0||dis[i]==-1)&&(st[i]&tmp)==tmp)
		ans.push_back(i);
	cout<<ans.size()<<'\n';
	for(int y:ans)cout<<y<<' ';
	return 0;
}