NOI2017D2T1 游戏

有 $ n $ 个变量，其中 $ d $ 个变量有三种可能的取值，其余变量有两种可能的取值。

另有 $ m $ 条限制关系，形如：若 $ x $ 的值是 $ a $ 那么 $ y $ 的值必须是 $ b $

求一组可能的解，或说明无解。

$ n\le 5\times 10^4,m\le 10^5,d\le 8 $

my sol

其实将题意化简到上面这样就很显然了。如果没有 $ d\le 8 $ 的限制，那么原问题是NP的。

但事实上大多数点都只有两种取值。

考虑 $ 2^d $ 枚举这 $ d $ 个点的取值，一种是强制不取第三个值，另一种是取且仅取第三个值。之后就变成了 2SAT 问题，tarjan 求解即可。

复杂度 $ \mathcal O(2^d\times (n+m)) $ 在loj上最长点仅16ms，loj永远滴神！

PS:在2SAT中，若要强制 $ x $ 只能取 $ x $ 而不取 $ x’ $ ,令 $ x’ $ 向 $ x $ 连边即可。

#define MAXN 200011
struct edge{int v,nxt;}e[MAXN<<1|1];
int cnt=0,last[MAXN];
void adde(int u,int v){e[++cnt].v=v,e[cnt].nxt=last[u],last[u]=cnt;}

int dfn[MAXN],low[MAXN],top=0,s[MAXN],scc[MAXN], cur=0,scnt=0;
bool ins[MAXN];
void tarjan(int u)
{
    dfn[u]=low[u]=++cur;
    s[++top]=u,ins[u]=1;
    for(int i=last[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(!dfn[v])tarjan(v),umin(low[u],low[v]);
        else if(ins[v])umin(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        ++scnt;
        while(s[top]!=u)scc[s[top]]=scnt,ins[s[top]]=0,--top;
        scc[s[top]]=scnt,ins[s[top]]=0,--top;
        // printf("SCC[%d]=%d\n",u,scnt);
    }
}
char a[MAXN];
struct tuple{int u,x,v,y;}ed[MAXN];
void clear(int n)
{
    cnt=cur=scnt=0;
    for(int i=1;i<=n+n;++i)last[i]=dfn[i]=low[i]=scc[i]=0;
}
void make_graph(int n,int m)
{
    for(int i=1;i<=m;++i)
    {
        int u=ed[i].u,x=ed[i].x,v=ed[i].v,y=ed[i].y;
        if(x==(a[u]-'a'))continue;
        if(y==(a[v]-'a')){adde(u+n*(x==(a[u]-'a'+1)%3),u+n*(x==(a[u]-'a'+2)%3));continue;}
        adde(u+n*(x==(a[u]-'a'+1)%3),v+n*(y==(a[v]-'a'+1)%3));
        adde(v+n*(y==(a[v]-'a'+2)%3),u+n*(x==(a[u]-'a'+2)%3));
    }
}
int pos[MAXN];
int main()
{
    // freopen("game2.in","r",stdin);
    int n=read(),d=read();d=0;
    scanf("%s",a+1);
    for(int i=1;i<=n;++i)
        if(a[i]=='x')pos[++d]=i;
    int m=read();
    for(int i=1;i<=m;++i)
    {
        ed[i].u=read(),ed[i].x=getchar()-'A';
        ed[i].v=read(),ed[i].y=getchar()-'A';
    }
    for(int s=0;s<(1<<d);++s)
    {
        clear(n);
        for(int i=1;i<=d;++i)
            if(s&(1<<(i-1)))a[pos[i]]='a',adde(n+pos[i],pos[i]);
            else a[pos[i]]='c';
        make_graph(n,m);
        for(int i=1;i<=n+n;++i)
            if(!dfn[i])tarjan(i);
        bool fail=0;
        for(int i=1;i<=n;++i)
            if(scc[i]==scc[n+i])fail=1;
        if(fail)continue;
        for(int i=1;i<=n;++i)
            if(scc[i]<scc[n+i])putchar((a[i]-'a'+2)%3+'A');
            else putchar((a[i]-'a'+1)%3+'A');
        return 0;
    }
    puts("-1");
    return 0;
}