2-Sat

1/************************************************************************* 2 > File Name: code/cf/#315/E.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月15日 星期六 13时48分36秒 6 ************************************************************************/ 7#include<iostream> 8#include<iomanip> 9#include<cstdio> 10#include<algorithm> 11#include<cmath> 12#include<cstring> 13#include<string> 14#include<map> 15#include<set> 16#include<queue> 17#include<vector> 18#include<stack> 19#define y0 abc111qqz 20#define y1 hust111qqz 21#define yn hez111qqz 22#define j1 cute111qqz 23#define tm crazy111qqz 24#define lr dying111qqz 25using namespace std; 26#define REP(i, n) for (int i=0;i<int(n);++i) 27typedef long long LL; 28typedef unsigned long long ULL; 29const int inf = 0x7fffffff; 30const int N=5E2+7; 31int flag[N],flag2[N]; 32int f[N][N]; 33int a[N]; 34char s[N]; 35int ans[N]; 36int len,n,m; 37char s1[13],s2[13]; 38int p1,p2,q1,q2,dq1,dq2; 39void add(int p,int q,int flag[]) 40{ 41 int dq = q * n + p;//找到元辅音状态为q，第p的点的下标 42 for (int i=1;i<=2*n;++i) 43 { 44 if (f[dq][i]==0) continue; 45 flag[i]=1;//找到所有由dp出发的边指向的点，表示选了dp点一定要选的点。 46 } 47} 48bool check(int flag[]) 49{ 50 for (int i=1;i<=n;++i) 51 if (flag[i]==1&&flag[i+n]==1) return false; //判断是否存在矛盾 52 //（选了j点后，既要选择某点k的元音，也要选择某点k的辅音）　53 return true; 54} 55bool dfs(int pos,int x) 56{ 57 if (pos>n) return true;//如果能形成一个长度为n的单词，说明这种语言有word 58 bool g[2]; 59 g[0]=g[1]=false; 60 for (int i=x;i<=len;++i)//从当前字母x往后枚举 61 { 62 for (int j=1;j<=2*n;++j) flag2[j]=flag[j];//为了不影响原始数组，复制一个布尔数组出来。 63 add(pos,a[i],flag2);//找到所有选了pos点一定要选的点 64 if (check(flag2)&&(!g[a[i]])) 65 { 66 g[a[i]]=true; 67 for (int j=1;j<=2*n;++j) flag[j]=flag2[j]; 68 ans[pos]=i;//将第pos位置的字母变成i 69 if (dfs(pos+1,1)) return true; 70 else return false;//只要有一位找不到合适的字母形成单词，那么肯定就构不成单词。 71 } 72 } 73 return false; 74} 75int main() 76{ 77 scanf("%s",s); 78 len=strlen(s); //0表示辅音，１表示原因，下同。 79 for (int i=1;i<=len;++i)//len 表示字母表中一共有的字母的个数 80 { 81 if (s[i-1]=='V') 82 { 83 a[i] = 0; 84 } 85 else 86 { 87 a[i] = 1; 88 } 89 } 90 memset(f,0,sizeof(f)); 91 scanf("%d%d",&n,&m); 92 for (int i=1;i<=m;++i)//1..n表示元音的点，n+1..2*n 表示辅音的点 93 { 94 scanf("%d",&p1); 95 scanf("%s",s1); 96 if (s1[0]=='V') q1=0;else q1=1; 97 scanf("%d",&p2); 98 scanf("%s",s2); 99 if (s2[0]=='V') q2=0;else q2=1; 100 dq1=q1*n+p1;dq2=q2*n+p2;//找到这组关系对应的点。 101 f[dq1][dq2]=1;//连一条由dq1指向dq2的边，表示如果选了dp1点，那么一定选dp2点　102 dq1=(1-q2)*n+p2;dq2=(1-q1)*n+p1;//找到逆否命题对应的点　103 // （"如果选１，一定选２"的逆否命题是，"如果不选２，一定不选１"） 104 f[dq1][dq2]=1; //在连一条边 105 } 106 for (int i=1;i<=2*n;++i) f[i][i]=1; 107 for (int k=1;k<=2*n;++k)//floyd ，把所有间接相连的边直接相连 108 { 109 for (int i=1;i<=2*n;++i) 110 for (int j=1;j<=2*n;++j) 111 f[i][j]|=f[i][k]&f[k][j]; 112 } 113 scanf("%s",s+1); 114 bool ok=false; 115 for (int i=n;i>=0;--i) //倒着扫，每次只改变最后一位的字母，字母从小往大枚举 //这样就可以保证字典序最小。 116 { 117 memset(flag,0,sizeof(flag)); 118 for (int j=1;j<=i;++j) 119 { 120 add(j,a[s[j]-'a'+1],flag); 121 ans[j]=s[j]-'a'+1; 122 } 123 if (!check(flag)) continue; 124 if (dfs(i+1,s[i+1]-'a'+1+1)) 125 { 126 ok=true; 127 break; 128 } 129 } 130 if (!ok) printf("-1\n"); 131 else 132 { 133 for (int i=1;i<=n;++i) printf("%c",ans[i]+'a'-1); 134 } 135 return 0; 136}