如果不看 $x$ 赛场的话,剩下的三个赛场显然每个赛场只有两个赛车选择项,也就是说这样就变成了裸的 $2-sat$ ,直接做就好了。

如果加入有三个赛车选择项的 $x$ 赛场的话,显然就不好用 $2-sat$ 做了,难不成用 $3-sat$ ?

其实,如果 $x$ 只有两个赛车选择项的话一样是可以做的,我们考虑枚举每一个 $x$ 赛场所禁用的那个赛车,这样子就可以 $2-sat$ 了,不过这样 $dfs$ 的复杂度是 $3^d$ 的,爆炸了......

但是最终情况就是每一个 $x$ 赛场都要有过 $A,B,C$ 三种赛车的选择项,那么在禁掉 $A,B$ 的时候,剩下的赛车分别是 $B,C$ 和 $A,C$ ,这已经包含 $A,B,C$ 三种赛车了,所以我们的 $dfs$ 只有两个分支了......复杂度就是 $2^d$ ,过去了。

考虑 $2-sat$ 怎么做,首先对于一组限制,如果 $i$ 选了 $h_i$ ,$j$ 就必须选 $h_j$ 。反之如果 $j$ 没选 $h_j$ ,那么 $i$ 就一定不能选择 $h_i$ ,这样连边就好了。注意如果 $j$ 不能选 $h_j$ 的话,$i$ 直接连 $i+n$ 即可。输出方案的话,对于一个 $i$ 点,我们只要对缩点后的图中拓扑一下,然后看 $i$ 所在的强连通分量和 $i+n$ 所在的强连通分量谁拓扑序更小谁就是答案。当然 $tarjan$ 已经按照拓扑序来了......所以直接判就好了。

细节多,看代码。

Code:

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

const int N=1e5+2;
const int M=4e5+2;

char S[N],No[N];
int n,d,m,book,t[N],head[N],cnt;
struct Edge{int nxt,to;} G[M];
struct Stint{int i,j;char hi,hj;} E[M];
int bel[N],dfn[N],low[N],hep[N],siz[N],tot,top,now;

void add(int u,int v) {
    G[++cnt]=(Edge){head[u],v},head[u]=cnt;
}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch))  x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

void Tarjan(int u) {
    low[u]=dfn[u]=++now,hep[++top]=u;
    for(int i=head[u];i;i=G[i].nxt) {
        int v=G[i].to;
        if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
        else if(!bel[v]) low[u]=min(low[u],dfn[v]);
    }
    if(!(low[u]^dfn[u])) {
        bel[u]=++tot,siz[tot]=1;
        while(hep[top]^u)
            ++siz[tot],bel[hep[top--]]=tot;
        --top;
    }return;
}

int opposite(int u) {return u>n?u-n:u+n;}
int point_id(int u,char c) {
    /*
        点的编号的规则就是对于一个赛场,除去禁用的赛车
           后,剩下的赛车小的为i,大的为i+n.
    */
    if(S[u]=='a') return c=='B'?u:n+u;
    if(S[u]=='b'||S[u]=='c') return c=='A'?u:n+u;
    return c=='C'?u+n:u;
}
bool sol() {
    cnt=tot=now=0;
    for(int i=1;i<=(n<<1);++i) bel[i]=head[i]=dfn[i]=0;
    for(int i=1;i<=m;++i)
        if(S[E[i].i]!='x'&&S[E[i].j]!='x') {
            /*如果E[i].i本身就不可以选择对应赛车的话直接跳*/
            if(S[E[i].i]-32==E[i].hi) continue;
            int u=point_id(E[i].i,E[i].hi);/*得到点编号*/
            /*如果E[i].j不可以选择对应赛车的话那么u无解*/
            if(S[E[i].j]-32==E[i].hj) {add(u,opposite(u));continue;}
            int v=point_id(E[i].j,E[i].hj);
            /*按要求连边*/
            add(u,v),add(opposite(v),opposite(u));
        } else {
            char si=S[E[i].i],sj=S[E[i].j];
            if(si=='x'&&sj=='x') {
                /*
                    注意这里禁掉的赛车变了,x的那一方就判断一下当前
                    dfs无法使用的赛车,其他的按照上面即可
                */
                if(No[t[E[i].i]]==E[i].hi) continue;
                int u=point_id(E[i].i,E[i].hi);
                if(No[t[E[i].j]]==E[i].hj) {add(u,opposite(u));continue;}
                int v=point_id(E[i].j,E[i].hj);
                add(u,v),add(opposite(v),opposite(u));
            } else if(si=='x'&&sj!='x') {
                if(No[t[E[i].i]]==E[i].hi) continue;
                int u=point_id(E[i].i,E[i].hi);
                if(S[E[i].j]-32==E[i].hj) {add(u,opposite(u));continue;}
                int v=point_id(E[i].j,E[i].hj);
                add(u,v),add(opposite(v),opposite(u));
            } else if(si!='x'&&sj=='x') {
                if(S[E[i].i]-32==E[i].hi) continue;
                int u=point_id(E[i].i,E[i].hi);
                if(No[t[E[i].j]]==E[i].hj) {add(u,opposite(u));continue;}
                int v=point_id(E[i].j,E[i].hj);
                add(u,v),add(opposite(v),opposite(u));
            }
        }
    /*2-sat基础不再赘述*/
    for(int i=1;i<=(n<<1);++i) if(!dfn[i]) Tarjan(i);
    for(int i=1;i<=n;++i) if(bel[i]==bel[i+n]) return false;
    for(int i=1,j=0;i<=n;++i)
        if(S[i]=='a') printf("%c",bel[i]<bel[i+n]?'B':'C');
        else if(S[i]=='b') printf("%c",bel[i]<bel[i+n]?'A':'C');
        else if(S[i]=='c') printf("%c",bel[i]<bel[i+n]?'A':'B');
        else if(S[i]=='x') {/*可以简洁点但是懒得改了(QwQ)*/
            char c=No[++j]=='A'?'B':'A';
            printf("%c",bel[i]<bel[i+n]?c:'C');   
        }
    return true;
}

void dfs(int step) {
    if(step>d) {
        if(book) exit(0);
        else book=sol();
        return;
    } 
    No[step]='A',dfs(step+1),/*两个分支*/
    No[step]='B',dfs(step+1);
}

int main() {
    IN(n),IN(d),scanf("%s",S+1);
    for(int i=1,j=0;i<=n;++i) if(S[i]=='x') t[i]=++j;
    char op1[2],op2[2];
    IN(m);
    for(int i=1;i<=m;++i)
        scanf("%d%s%d%s",&E[i].i,op1,&E[i].j,op2),E[i].hi=op1[0],E[i].hj=op2[0];
    dfs(1);
    if(!book) puts("-1");/*无解*/
    return 0;
}
最后修改:2019 年 06 月 04 日 05 : 44 PM