D42 2-SAT+二进制枚举 P3825 [NOI2017] 游戏

视频链接：

P3825 [NOI2017] 游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 2-SAT+二进制枚举 O(2^8*(n+m))
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100005;
int head[N],to[N<<1],ne[N<<1],idx;
int dfn[N],low[N],tim,stk[N],top,scc[N],cnt;
int n,d,m,pos[10]; //pos:x位置
char s[N];         //地图
struct OP{int x,y;char A,B;}op[N<<1]; //条件

void add(int a,int b){
  to[++idx]=b,ne[idx]=head[a],head[a]=idx;
}
void tarjan(int x){
  dfn[x]=low[x]=++tim;
  stk[++top]=x;
  for(int i=head[x];i;i=ne[i]){
    int y=to[i];
    if(!dfn[y]){ //若y尚未访问
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if(!scc[y]) //若y已访问且未处理
      low[x]=min(low[x],dfn[y]);
  }
  
  if(low[x]==dfn[x]){ //若x是SCC的根
    ++cnt;
    for(int y=-1;y!=x;)
      scc[y=stk[top--]]=cnt;
  }
}
int get(int x,char c,int t){
  return 'A'+(s[x]-'a'+t)%3==c?x:x+n;
}
char put(int x,int t){
  return 'A'+(s[x]-'a'+t)%3;
}
bool solve(){
  memset(head,0,sizeof head);
  memset(dfn,0,sizeof dfn);
  memset(scc,0,sizeof scc);
  idx=tim=top=cnt=0;
  for(int i=0;i<m;i++){
    int x=op[i].x-1,y=op[i].y-1;
    char A=op[i].A,B=op[i].B;
    if(s[x]!=A+32){
      if(s[y]!=B+32){
        add(get(x,A,1),get(y,B,1)); //A1→B1
        add(get(y,B,2),get(x,A,2)); //B2→A2
      }
      else add(get(x,A,1),get(x,A,2)); //A1→A2
    }
  }
  for(int i=0;i<2*n;i++)if(!dfn[i])tarjan(i);
  for(int i=0;i<n;i++)
    if(scc[i]==scc[i+n]) return false;
  for(int i=0;i<n;i++)
    if(scc[i]<scc[i+n]) putchar(put(i,1));
    else putchar(put(i,2));
  return true;
}
int main(){
  scanf("%d%d %s %d",&n,&d,s,&m);
  for(int i=0;i<m;i++)
    scanf("%d %c %d %c",&op[i].x,&op[i].A,&op[i].y,&op[i].B);
  for(int i=0,j=0;i<n;i++)
    if(s[i]=='x') pos[j++]=i; //x位置
  for(int i=0;i<1<<d;i++){
    for(int j=0;j<d;j++)
      s[pos[j]]=(i>>j&1)?'a':'b'; //x→a或b
    if(solve()) return 0;
  }
  puts("-1"); return 0;
}