【NOI2017】游戏（搜索，2-sat）

题面

BZOJ的SPJ是假的

题解

如果没有\(x\)地图的影响

这就是一个裸的\(2-sat\)问题

但是现在有不超过\(8\)个\(x\)地图的影响

我们不难想到枚举\(x\)地图的状态再来\(2-sat\)判断剩余是否可行。

这样的复杂度是\(O(3^dn)\)，稍微算一下发现这个复杂度有点假

考虑如何优化，我们枚举\(x\)地图不连什么

表面上看起来还是\(O(3^dn)\)

但是，当他等价于\(a,b\)两种地图时，\(2^d\)种方案中一定会包含着最后的解，也就是说，\(a,b\)两种地图替换\(x\)的所有状态，等价于\(a,b,c\)三种地图替换\(x\)

这样的复杂度是\(O(2^dn)\)

现在考虑\(2-sat\)如何连边

对于限制\(i->j\)

显然直接连接\(i->j\)

并且，如果\(j'\)被选择，那么必须选择\(i'\)

所以，同时连接\(j'->i'\)

一些没有意义的连边可以直接省略。

至于输出方案，\(Tarjan\)求出来的强连通分量已经和拓扑序相关，因此没有必要重新建图拓扑排序

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define ll long long#define RG register#define MAX 333333inline int read(){ RG int x=0,t=1;RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}char g[MAX];struct Limit{int i,j;char a,b;}q[MAX];int n,D,m,pos[20];struct Line{int v,next;}e[MAX<<3];int h[MAX],cnt;int p[MAX];inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}bool fl;void Build(){ memset(h,0,sizeof(h));cnt=1;fl=true; for(int i=1;i<=n;++i) { p[i]=p[i+n]=p[i+n+n]=0; if(g[i]=='a')p[i+n]=i+n+n,p[i+n+n]=i+n; else if(g[i]=='b')p[i]=i+n+n,p[i+n+n]=i; else p[i]=i+n,p[i+n]=i; } for(int i=1;i<=m;++i) { int u=q[i].i,v=q[i].j; int a=q[i].a-65,b=q[i].b-65; if(u==v&&a==b)continue; if(g[u]-97==a)continue; if(g[v]-97==b){Add(u+a*n,p[u+a*n]);continue;} Add(u+a*n,v+b*n); Add(p[v+b*n],p[u+a*n]); }}int dfn[MAX],low[MAX],S[MAX],top;int gr,G[MAX],tim,ans[MAX];bool Ins[MAX];void Tarjan(int u){ dfn[u]=low[u]=++tim; S[++top]=u;Ins[u]=true; int v; for(int i=h[u];i;i=e[i].next) { v=e[i].v; if(!dfn[v])Tarjan(v),low[u]=min(low[u],low[v]); else if(Ins[v])low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { ++gr; do{v=S[top--];G[v]=gr;Ins[v]=false;}while(u!=v); }}void Calc(){ Build();gr=tim=0;if(!fl)return; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(G,0,sizeof(G)); for(int i=1;i<=n+n+n;++i)if(!dfn[i])Tarjan(i); for(int i=1;i<=n+n+n;++i)if(G[i]==G[p[i]])return; for(int i=1;i<=n;++i) { if(g[i]=='a')(G[i+n]