题目地址：洛谷：【P3825】[NOI2017]游戏 – 洛谷、BZOJ：Problem 4945. — [Noi2017]游戏

题目描述

狂野飙车是小 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’’（不含双引号）。

题意简述

你正在玩一个赛车游戏，一共有3种车型，每一场有不适合的车型，有的比赛没有不适合的车型，这种比赛的数量$\leq 8$。有一些限制条件，表示某场比赛如果使用某种车型，那么另一场比赛必须使用另种车型。求是否存在每场比赛采用的车型的安排符合上述所有条件。

输入输出格式

输入格式：
输入第一行包含两个非负整数 n,d 。
输入第二行为一个字符串 S 。 n,d,S 的含义见题目描述，其中 S 包含 n 个字符，且其中恰好 d 个为小写字母 x 。
输入第三行为一个正整数 m ，表示有 m 条用车规则。接下来 m 行，每行包含一个四元组 i,hi,j,hj ，其中 i,j 为整数， hi,hj 为字符a、b或c，含义见题目描述。

输出格式：
输出一行。
若无解输出 “-1’’（不含双引号）。
若有解，则包含一个长度为 n 的仅包含大写字母A、B、C的字符串，表示小 L 在这 n 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。

输入输出样例

输入样例#1：

3 1
xcc
1
1 A 2 B

输出样例#1：

ABA

说明

题解

本题可以使用2-SAT解决。
如果不存在可以使用三种的游戏，那么我们按如下方式建图。

1. 如果$h_i$是$i$不能用的车型，则不作任何操作；
2. 如果不满足1，且$h_j$是$j$不能用的车型，则标注$(i, h_i)$为“不可能选择”的方案，即连接它与$i$的另外一个选项；
3. 如果不满足1和2，则有两种选择，即选$(i, h_i)$必须选$(j, h_j)$，选$j$的另外一个选项必须选$i$的另外一个选项，如此建边即可。

跑完2-SAT输出方案就好。对于可以使用三种车型的游戏，则枚举它不能使用某种车型，就转变为类似普通游戏的模型，枚举到一个方案判断一次即可。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>
#include <stack>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 100005;

int n, m;
char s[MAXN], s1[MAXN];

struct Info {
    int i, j;
    char hi, hj;
} infos[MAXN];

struct Edge {
    int to, nxt;
} gra[MAXN << 1], gran[MAXN << 1];
int head[MAXN], headn[MAXN], tot, totn;

inline void addedge(int u, int v) {
    gra[tot] = Edge {v, head[u]}; head[u] = tot++;
}

inline void addedgen(int u, int v) {
    gran[totn] = Edge {v, headn[u]}; headn[u] = totn++;
}

inline void reset() {
    tot = totn = 0;
    memset(head, -1, sizeof(head));
    memset(headn, -1, sizeof(headn));
}

int dfn[MAXN], low[MAXN], clk, sno[MAXN], scc, op[MAXN];
std::stack<int> sta;
bool insta[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    sta.push(u); insta[u] = true;
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        scc++;
        int p;
        do {
            p = sta.top(); sta.pop();
            insta[p] = false;
            sno[p] = scc;
        } while(p != u);
    }
}

int deg[MAXN];
std::queue<int> que;
int mark[MAXN];

void dfs_mark(int u) {
    if(mark[u]) return;
    mark[u] = -1;
    for(int i = headn[u]; ~i; i = gran[i].nxt) {
        int v = gran[i].to;
        dfs_mark(v);
    }
}

inline void toposort() { 
    for(int i = 1; i <= scc; i++) {
        if(!deg[i]) que.push(i);
    }
    while(!que.empty()) {
        int u = que.front(); que.pop();
        if(mark[u]) continue;
        mark[u] = 1;
        dfs_mark(op[u]);
        for(int i = headn[u]; ~i; i = gran[i].nxt) {
            int v = gran[i].to;
            if(!--deg[v]) que.push(v);
        }
    }
}

inline int id(int x, char y) {
    if(s1[x] == 'a') {
        if(y == 'B') return x;
        else return x + n;
    } else {
        if(y == 'A') return x;
        else return x + n;
    }
}

inline char choice(int x) {
    int xx = x > n ? x - n : x;
    if(s1[xx] != 'a' && id(xx, 'A') == x) return 'A';
    else if(s1[xx] != 'b' && id(xx, 'B') == x) return 'B';
    else if(s1[xx] != 'c' && id(xx, 'C') == x) return 'C';
}

inline int oppo(int x) {
    if(x > n) return x - n;
    else return x + n;
}

inline bool work() {
    reset();
    for(int i = 1; i <= m; i++) {
        Info x = infos[i];
        if(s1[x.i] == tolower(x.hi)) {
            continue;
        } else if(s1[x.j] == tolower(x.hj)) {
            addedge(id(x.i, x.hi), oppo(id(x.i, x.hi)));
        } else {
            addedge(id(x.i, x.hi), id(x.j, x.hj));
            addedge(oppo(id(x.j, x.hj)), oppo(id(x.i, x.hi)));
        }
    }
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    for(int i = 1; i <= n * 2; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int i = 1; i <= n; i++) {
        if(sno[i] == sno[i + n]) return false;
        op[sno[i]] = sno[i + n];
        op[sno[i + n]] = sno[i];
    }
    memset(deg, 0, sizeof(deg));
    for(int u = 1; u <= n * 2; u++) {
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(sno[u] != sno[v]) {
                addedgen(sno[v], sno[u]);
                deg[sno[u]]++;
            }
        }
    }
    toposort();
    for(int i = 1; i <= n; i++) {
        if(mark[sno[i]] == 1) putchar(choice(i));
        else putchar(choice(i + n));
    }
    return true;
}

bool dfs_s(int step) {
    if(step > n) return work();
    if(s[step] != 'x') {
        s1[step] = s[step];
        if(dfs_s(step + 1)) return true;
    } else {
        s1[step] = 'a';
        if(dfs_s(step + 1)) return true;
        s1[step] = 'b';
        if(dfs_s(step + 1)) return true;
        s1[step] = 'c';
        if(dfs_s(step + 1)) return true;
    }
}

int main() {
    n = readint(); readint();
    for(int i = 1; i <= n; i++) {
        s[i] = readsingle();
    }
    m = readint();
    for(int i = 1; i <= m; i++) {
        infos[i].i = readint();
        infos[i].hi = readsingle();
        infos[i].j = readint();
        infos[i].hj = readsingle();
    }
    if(!dfs_s(1)) puts("-1");
    return 0;
}