自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 22:46:10，当前版本为作者最后更新于2023-04-05 16:04:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

能隐约感觉到，应该是通过某种方式把所有的钥匙都收集起来，然后通过某种方式把它们放到要放的地方。

Subtask 1

问你是否能收集到所有钥匙。

这个可以通过搜索的方式解决。你在第一个房间会有一个钥匙，然后能进入所有的和这个钥匙颜色相同的相邻的房间，获得新的钥匙。

唯一麻烦的事情是，如果 $1$ 旁边有一个颜色为 $2$ 的房间，但是一时半会儿拿不到钥匙 $2$，不过迟早能拿到，这时候这个颜色为 $2$ 的房间如何保证能搜索到。

解决方法是，开一个额外的 set 记录每种颜色有哪些点是等待钥匙支援后能立刻进入的。

复杂度 $O(n \log n)$。

Subtask 2

假设你有了所有的钥匙，如何重新分配。

考虑把目标当做现有的钥匙，重新进行 Subtask 1 的工作。我们惊奇的发现，如果把拿钥匙看做放钥匙，那么倒着走这个路线就是合法的。

所以可以类似 Subtask 1 的方法进行判断。

唯一不同的是，如果这个点的钥匙和颜色相同，在 Subtask 1 中如果没有持有相同颜色的钥匙就进不去，但是 Subtask 2 中进去就是合理的。

还有一个小细节，这个图可能不连通。如果 Subtask 1 中一个点不能到达，必须要求它的起始状态和目标状态相同，而且在 Subtask 2 中不能到达它。

代码：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int T,n,m,c[MAXN],k[MAXN],s[MAXN],f[MAXN],tag[MAXN],flg[MAXN],extra[MAXN];
//flg:Whether or not I own the key colored i
//tag:Whether or not I have visited the point(the one on the graph)
vector<int> G[MAXN];
set<int> q[MAXN];
int check(int op) {
	ffor(i,1,n) q[i].clear(),flg[i]=0,tag[i]=0;
	queue<int> d; d.push(1); flg[k[1]]=1;
	while(!d.empty()) {
		int u=d.front(); d.pop();
		if(tag[u]) continue;
		tag[u]=1; if(!flg[k[u]]) {
			flg[k[u]]=1;
			for(auto v:q[k[u]]) if(!tag[v]) d.push(v);
			q[k[u]].clear();
		}
		for(auto v:G[u]) {
			if(tag[v]) continue;
			if(extra[v]) continue;
			if(op&&c[v]==k[v]) {d.push(v);continue;}
			if(flg[c[v]]) d.push(v);
			else q[c[v]].insert(v);
		}
	}
	if(!op) {
		ffor(i,1,n) if(!tag[i]) extra[i]=1;	
	}
	ffor(i,1,n) if(!tag[i]&&s[i]!=f[i]) return 0;
	return 1;
}
void work(void) {
	cin>>n>>m;
	ffor(i,1,n) extra[i]=0;
	ffor(i,1,n) G[i].clear(),cin>>c[i];
	ffor(i,1,n) cin>>s[i];
	ffor(i,1,n) cin>>f[i];
	ffor(i,1,m) {
		int u,v; cin>>u>>v;
		G[u].push_back(v),G[v].push_back(u);	
	}
	int flg=1;
	ffor(i,1,n) k[i]=s[i];
	flg&=check(0);
	ffor(i,1,n) k[i]=f[i];
	flg&=check(1);
	if(flg) cout<<"YES\n"; else cout<<"NO\n";
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T; while(T--) work();
	return 0;
}