题解：P9189 [USACO23OPEN] Custodial Cleanup G

· · 题解

前言

很妙的题，属于做不倒系列，题目传送门。

做法

首先可以感觉到，先把所有钥匙收集起来，再把它们放到相应位置，这样一定更优。因为这样能达到的点尽可能多，也不会使后面放钥匙更劣。

现在考察能到达哪些点。不难发现可以用 BFS 实现，对于还没有相应钥匙的点，可以用桶存起来。如果有了该颜色的钥匙，就把桶清空并加入队列，将该钥匙打上可行标记。时间复杂度为 \mathcal O(n)。

现在再考虑放钥匙操作。这时惊奇地发现，将 F_i 视为新钥匙，对于放钥匙的步骤，倒着做就是合法的拿新钥匙操作，即上面 BFS 的过程。故也可以用 BFS 来找出哪些点可以放钥匙。

唯一不同在于，在第二种 BFS 中，如果没有该颜色的新钥匙，只要 C_i=F_i 也可以进入该点，因为放钥匙时，实际上刚好存在这个颜色。

最后只需要判断，第一次 BFS 能达到的点，第二次 BFS 是否也能到达即可。

还剩一些小细节：

:::info[code]

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=1e5+10;

vector <int> e[N],tong[N];
int c[N],s[N],f[N];
bool vis[N],good[N],book[N];
queue <int> q;

void read(){}
template <typename T,typename ...Args>
void read(T &x,Args &...args)
{
    x=0;  char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';  ch=getchar();}
    read(args...);
}

inline void solve()
{
    int n,m,x,y,now;  read(n,m);
    for(int i=1;i<=n;i++) e[i].clear(),tong[i].clear(),vis[i]=book[i]=good[i]=false;
    for(int i=1;i<=n;i++) read(c[i]);
    for(int i=1;i<=n;i++) read(s[i]);
    for(int i=1;i<=n;i++) read(f[i]);
    for(int i=1;i<=m;i++) read(x,y),e[x].emplace_back(y),e[y].emplace_back(x);
    good[s[1]]=vis[1]=true;  q.push(1);
    while(!q.empty())
    {
        now=q.front();  q.pop();  good[s[now]]=true;
        for(int i:tong[s[now]])
            if(!vis[i]) q.push(i),vis[i]=true;
        for(int i:e[now])
        {
            if(vis[i]) continue;
            if(good[c[i]]) q.push(i),vis[i]=true;
            else tong[c[i]].emplace_back(i);
        }
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]&&s[i]!=f[i]) return puts("NO"),void();
    for(int i=1;i<=n;i++) tong[i].clear(),good[i]=false;
    good[f[1]]=book[1]=true;  q.push(1);
    while(!q.empty())
    {
        now=q.front();  q.pop();  good[f[now]]=true;
        for(int i:tong[f[now]])
            if(!book[i]) q.push(i),book[i]=true;
        for(int i:e[now])
        {
            if(book[i]||!vis[i]) continue;
            if(good[c[i]]||c[i]==f[i]) q.push(i),book[i]=true;
            else tong[c[i]].emplace_back(i);
        }
    }
    for(int i=1;i<=n;i++)
        if(vis[i]&&!book[i]&&f[i]!=s[i]) return puts("NO"),void();
    puts("YES");
}

int main()
{
    int t;  read(t);
    while(t--) solve();
    return 0;
}

:::