P8276 [USACO22OPEN] Hoof and Brain P

Kubic · 2022-04-03 19:27:18 · 题解

牛题，场上硬磕 2.5h 淦出来了。

先对反图进行拓扑排序，如果一个点在拓扑排序的过程中入度变为了 0，那么称这个点为好点。

如果询问的两个点中有至少一个是好点，那么显然 Brain 必胜。

由于 Hoof 一旦走到好点上就死定了，所以我们可以直接把所有好点都删除，考虑这个新图。

显然这个新图中每个点出度都不为 0。

我们考虑给每一个点 u 染一种颜色 col_u。进行如下过程：

初始时每个点 u 都有 col_u=u。
如果 u 的所有出边指向的 v 颜色全部都相同，那么将所有颜色为 col_u 的点的颜色改为 col_v。
重复上一步直到颜色不再变化。

先给出结论：如果初始两个点颜色相同，则 Brain 必胜，否则 Hoof 必胜。

为什么它是对的呢？

我们考虑一个点的颜色的实际意义：假设有一颗棋子在 u 上，令 Brain 不断地钦定这颗棋子，那么它无论怎么移动一定在某个时刻经过了 col_u 这个点。

分两种情况分别讨论：

如果初始两个点颜色都为 c，那么我们可以让它们在 c 这个点上堵死。因此 Brain 必胜。
如果初始两个点颜色分别为 c_1,c_2，那么无论 Brain 怎么选，Hoof 都有至少一种走法可以使得走完后两个点颜色不同。因此 Hoof 必胜。

有了这些结论后，我们就只需要快速维护每个点的 col 即可。

这一部分就很容易了，只需要对于每个点维护它的出边指向的点的颜色种数，每次启发式合并两个集合即可。

时间复杂度 O(m\log n)。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define pb push_back
int n,m,c,dg[N],q[N],rt[N],w1[N],ps[N];bool vs[N];
vector<int> e[N],e1[N],vc[N];map<int,int> w[N];
void upd(int u,int vl)
{
    for(auto v:e[u]) if(!vs[v])
    {
        --w[v][rt[u]];if(!w[v][rt[u]]) --w1[v];
        if(!w[v][vl]) ++w1[v];++w[v][vl];
        if(w1[v]==1) vs[v]=1,q[++q[1]]=v;
    }rt[u]=vl;
}
void merge(int u,int v)
{
    u=rt[u];v=rt[v];if(u==v) return;
    if(vc[u].size()>vc[v].size()) swap(u,v);
    for(auto i:vc[u]) upd(i,v),vc[v].pb(i);vc[u].clear();
}
int main()
{
    scanf("%d %d",&n,&m);q[0]=2;q[1]=1;
    for(int i=1,u,v;i<=m;++i)
        scanf("%d %d",&u,&v),e1[v].pb(u),++dg[u];
    for(int i=1;i<=n;++i) {vc[i].pb(i);if(!dg[i]) q[++q[1]]=i;}
    while(q[0]<=q[1])
    {
        int u=q[q[0]++];rt[u]=0;
        for(auto v:e1[u]) {--dg[v];if(!dg[v]) q[++q[1]]=v;}
    }q[0]=2;q[1]=1;
    for(int i=1;i<=n;++i) if(dg[i])
        for(auto j:e1[i]) if(dg[j]) e[i].pb(j),ps[j]=i;
    for(int i=1;i<=n;++i) if(dg[i])
    {rt[i]=i;for(auto j:e[i]) {if(!w[j][i]) ++w1[j];++w[j][i];}}
    for(int i=1;i<=n;++i) if(w1[i]==1) q[++q[1]]=i;
    while(q[0]<=q[1]) {int u=q[q[0]++];merge(u,ps[u]);}
    scanf("%d",&c);
    for(int i=1,u,v;i<=c;++i)
    {
        scanf("%d %d",&u,&v);u=rt[u];v=rt[v];
        if(!u || !v) putchar('B');else putchar(u==v?'B':'H');
    }return 0;
}