题目描述

狂野飙车是小 L最喜欢的游戏。与其他业余玩家不同的是，小L在玩游戏之余，还精于研究游戏的设计，因此他有着与众不同的游戏策略。小 L计划进行 n 场游戏，每场游戏使用一张地图，小L会选择一辆车在该地图上完成游戏。小L的赛车有三辆，分别用大写字母 A、B、C表示。
地图一共有四种，分别用小写字母 x、a、b、c表示。
其中，赛车 A不适合在地图 a 上使用，赛车B不适合在地图b上使用，赛车C不适合在地图c上使用，而地图x则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 d张。

n场游戏的地图可以用一个小写字母组成的字符串描述。
例如：S=xaabxcbc表示小 L 计划进行 8 场游戏，其中第 1场和第5场的地图类型是x，适合所有赛车，第2场和第3场的地图是 a，不适合赛车 A，第 4 场和第 7 场的地图是 b，不适合赛车 B， 第 6 场和第 8 场的地图是 c，不适合赛车 C。

小 L对游戏有一些特殊的要求，这些要求可以用四元组 (i,hi,j,hj) 来描述，表示若在第 i 场使用型号为 hi 的车子，则第 j 场游戏要使用型号为 hj的车子。

你能帮小 L选择每场游戏使用的赛车吗？

如果有多种方案，输出任意一种方案。

如果无解，输出 “−1”（不含双引号）。

题目链接：
https://www.acwing.com/problem/content/description/1034/

样例

略

算法1

代码更清晰，代价是时间和空间都变差了，与y总的比，时间和空间都增加约80%。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N=50005*6, M=500500;
int ver[M],nxt[M],head[N],tot=1,hbk[N],tbk;
int dfn[N],low[N],stk[N],scc[N],top,num,cnt;
bool ins[N];
char s[N/6];
int n,d,m,da[10],nd,idx[N/6][3][2];

void add(int a, int b) {
    ver[++tot]=b,nxt[tot]=head[a],head[a]=tot;
}

void tarjan(int x) {
    dfn[x]=low[x]=++num;
    stk[++top]=x, ins[x]=true;
    for(int i=head[x]; i; i=nxt[i]) {
        int y=ver[i];
        if(!dfn[y]) {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        } else if(ins[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]) {
        cnt++;
        int y;
        do {
            y=stk[top--];
            ins[y]=false;
            scc[y]=cnt;
        } while(x!=y);
    }
}

int id(int i,int a,bool t) {
    static int cnt=0;
    if(idx[i][a][t]==0)idx[i][a][t]=++cnt;
    return idx[i][a][t];
}

int main() {
    cin>>n>>d;
    scanf("%s",s);
    for(int i=0; i<n; i++) {
        if(s[i]=='x')
            da[nd++]=i;
        else {
            int a=s[i]-'a';
            int b=0+(a==0), c=2-(a==2);
            add(id(i,a,1),id(i,a,0)); //不用a
            add(id(i,b,0),id(i,c,1)); //不用b,就用c
            add(id(i,c,0),id(i,b,1)); //不用c,就用b
            add(id(i,b,1),id(i,c,0)); //用b,就不用c
            add(id(i,c,1),id(i,b,0)); //用c,就不用b       
        }
    }
    cin>>m;
    for(int k=0; k<m; k++) {
        int i,j;
        char a,b;
        scanf("%d %c%d %c",&i,&a,&j,&b);
        a-='A', b-='A';
        i--, j--;
        add(id(i,a,1),id(j,b,1)); //用了a就必须用b
        add(id(j,b,0),id(i,a,0)); //不用b，就不用a
    }
    memcpy(hbk,head,sizeof head);
    tbk=tot;

    for(int i=0; i<(1<<d); i++) {
        memcpy(head,hbk,sizeof head);
        tot=tbk;
        memset(dfn,0,sizeof dfn);
        num=cnt=top=0;
        for(int j=0; j<d; j++) {
            int k=da[j],a=0,b=1,c=2;
            if( (i>>j) & 1 ) {
                add(id(k,a,0),id(k,a,1)); //用a
                add(id(k,b,1),id(k,b,0)); //不用b
                add(id(k,c,1),id(k,c,0)); //不用c
            } else {
                add(id(k,a,1),id(k,a,0)); //不用a
                add(id(k,c,0),id(k,b,1)); //不用c就用b
                add(id(k,b,0),id(k,c,1)); //不用b就用c
                add(id(k,c,1),id(k,b,0)); //用c就不用b
                add(id(k,b,1),id(k,c,0)); //用b就不用c            
            }
        }
        for(int i=0; i<6*n; i++)
            if(!dfn[i]) tarjan(i);
        int succ=1;
        for(int i=0; i<n; i++)
            for(int j=0; j<3; j++)
                if(scc[ id(i,j,0) ] == scc[ id(i,j,1) ] )
                    j=3,i=n,succ=0;
        if(succ==0)continue;
        for(int i=0; i<n; i++) {
            for(int j=0; j<3; j++)
                if(j!=s[i]-'a' && scc[ id(i,j,1) ] < scc[ id(i,j,0) ] )
                    printf("%c",char('A'+j)), j=3;
        }
        return puts("") & 0;
    }
    puts("-1");
}