自动搬运

查看原文

来自洛谷，原作者为

	ClearluvXL 心碎小狗

搬运于2025-08-24 22:55:58，当前版本为作者最后更新于2024-11-13 18:26:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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