P9189 题解

· · 题解

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;
}