【BZOJ4945&&UOJ317】游戏（2-sat，拓扑序）

题意：
思路：
输出方案时有一个优秀的性质可以利用：
tarjan缩点之后点所属的分量编号是原图的反的拓扑序
所以只需要在两种方案内找到所属分量编号较小的那个就行了，用来满足(i,i')那个限制
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<map>
  8 #include<set>
  9 #include<queue>
 10 #include<vector>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef unsigned int uint;
 14 typedef unsigned long long ull;
 15 typedef pair<int,int> PII;
 16 typedef vector<int> VI;
 17 #define fi first
 18 #define se second
 19 #define MP make_pair
 20 #define N   310000
 21 #define M   410000
 22 #define eps 1e-8
 23 #define pi  acos(-1)
 24 #define oo  1e9
 25 
 26 int head[M],vet[M],nxt[M],flag[M],dfn[M],low[M],belong[M],stk[M],
 27     c[M],x[M],y[M],f[M][2],num[M][4],q[M],b[M],a[M],
 28     n,m,D,tot,top,ans,tim,s,id;
 29 char ch[M];
 30 
 31 void add(int a,int b)
 32 {
 33     nxt[++tot]=head[a];
 34     vet[tot]=b;
 35     head[a]=tot;
 36 }
 37 
 38 void tarjan(int u)
 39 {
 40     flag[u]=1;
 41     stk[++top]=u;
 42     dfn[u]=low[u]=++tim;
 43     int e=head[u];
 44     while(e)
 45     {
 46         int v=vet[e];
 47         if(!flag[v])
 48         {
 49             tarjan(v);
 50             low[u]=min(low[u],low[v]);
 51         }
 52          else if(!belong[v]) low[u]=min(low[u],low[v]);
 53         e=nxt[e];
 54     }
 55     if(dfn[u]==low[u])
 56     {
 57         belong[u]=++id;
 58         while(top&&stk[top]!=u)
 59         {
 60             belong[stk[top]]=id;
 61             stk[top--]=0;
 62         }
 63         stk[top--]=0;
 64     }
 65 }
 66  
 67 int solve()
 68 {
 69     
 70     for(int i=1;i<=s;i++) flag[i]=low[i]=dfn[i]=head[i]=belong[i]=0; 
 71     tot=0;
 72     for(int i=1;i<=m;i++)
 73      if(c[x[i]]!=f[i][0])
 74      {
 75          if(c[y[i]]==f[i][1]) 
 76          {
 77              int t1=num[x[i]][f[i][0]];
 78              int t2=num[x[i]][6-f[i][0]-c[x[i]]];
 79             add(t1,t2);
 80          }
 81           else
 82           {
 83               int t1=num[x[i]][f[i][0]]; 
 84             int t2=num[y[i]][f[i][1]];
 85             add(t1,t2);
 86               t1=num[y[i]][6-c[y[i]]-f[i][1]]; 
 87               t2=num[x[i]][6-c[x[i]]-f[i][0]];
 88               add(t1,t2);
 89               
 90           }
 91      }
 92     
 93     top=tim=id=0;
 94 
 95     for(int i=1;i<=s;i++)
 96      if(!flag[i]) tarjan(i);
 97      
 98 
 99     for(int i=1;i<=n;i++)
100     {
101         int x,y;
102         if(c[i]==1){x=2; y=3;}
103         if(c[i]==2){x=1; y=3;}
104         if(c[i]==3){x=1; y=2;}
105         if(belong[num[i][x]]==belong[num[i][y]]) return 0;
106     }
107     
108     for(int i=1;i<=n;i++) 
109     {
110         int x,y;
111         if(c[i]==1){x=2; y=3;}
112         if(c[i]==2){x=1; y=3;}
113         if(c[i]==3){x=1; y=2;}
114         int t;
115         if(belong[num[i][x]]<belong[num[i][y]]) t=x;
116          else t=y;
117         printf("%c",'A'+t-1);
118     }
119     return 1;
120 }
121 
122 void dfs(int k)
123 {
124     if(ans) return;
125     if(k==D+1)
126     {
127         if(solve()) ans=1;
128         return; 
129     }
130     
131     for(int i=1;i<=2;i++)
132     {
133         c[b[k]]=i;
134         dfs(k+1);
135         c[b[k]]=0;
136     }
137 }
138 
139 int main()
140 {
141 
142     scanf("%d%d",&n,&D);
143     scanf("%s",ch+1);
144     for(int i=1;i<=n;i++)
145     {
146         if(ch[i]=='x') a[i]=4;
147          else a[i]=ch[i]-'a'+1;
148     }
149     D=0;
150     for(int i=1;i<=n;i++) 
151      if(a[i]==4) b[++D]=i;
152     for(int i=1;i<=n;i++) c[i]=a[i];
153         
154     s=0;
155     for(int i=1;i<=n;i++)
156      for(int j=1;j<=3;j++) num[i][j]=++s;
157     
158     scanf("%d",&m);
159     char c1[5];
160     char c2[5];
161     for(int i=1;i<=m;i++) 
162     {
163         scanf("%d%s%d%s",&x[i],&c1,&y[i],&c2);
164         f[i][0]=c1[0]-'A'+1;
165         f[i][1]=c2[0]-'A'+1;
166         
167     }
168     ans=0;
169     dfs(1);
170     if(!ans) printf("-1
"); 
171     return 0;
172 }