题意：
有一些部长需要对某些账单进行投票。
一个部长最多对4个账单进行投票，且每票对一个账单通过，要么否决。
问是否存在一个方案使得所有部长有超过半数的投票被通过，如果有，那么说明哪些账单的决定是明确的，哪些是不明确的；否则说明不可能。
思路：
2-SAT。
一开始觉得这是一个k-SAT问题，但是因为有着所有部长的投票有超过半数被通过这个条件存在，所以可以简化。
对于一票或者两票的部长，那么所有条件都要被满足，意味着某些账单的决定是确定。
如何表示一个条件是确定的呢，这是从这个题中学习到的一点，不是简单的标记这个条件的真假，而是从自己向自己的对立面连边，如果在搜索的过程中，发现自己和自己的对立面均被标记，那么就产生矛盾从而不满足条件了。
然后是对于3票或者4票的部长，要超过一半，如果一旦一个账单取相反的决定，那么其它账单都要取与输入相同的决定才能保证查过一半，再根据这个条件连边。
之后再解决如何确定一个账单的决定是否明确，对于一个账单，如果标记为通过能找到方案，否决也能找到方案，那么这个账单的决定就是不明确的，否则就可以判断其是明确的。在每一次标记了一个条件进行搜索之后，都必须将这个过程中标记过的点全部初始化，才能保证下一次搜索的正确。
代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <string> 4 #include <iostream> 5 #include <vector> 6 #include <algorithm> 7 using namespace std; 8 9 const int maxn = 505; 10 11 struct twosat 12 { 13 int n; 14 vector<int> g[maxn*2]; 15 bool mark[maxn*2]; 16 int s[maxn*2],c; 17 int ty[maxn]; 18 19 bool dfs(int x) 20 { 21 if (mark[x^1]) return false; 22 if (mark[x]) return true; 23 24 mark[x] = true; 25 26 s[c++] = x; 27 28 for (int i = 0;i < g[x].size();i++) 29 { 30 if (!dfs(g[x][i])) return false; 31 } 32 33 return true; 34 } 35 36 void add_clause(int x,int xval,int y,int yval) 37 { 38 x = x * 2 + xval; 39 y = y * 2 + yval; 40 41 g[x^1].push_back(y); 42 } 43 44 void init(int n) 45 { 46 this -> n = n; 47 memset(mark,0,sizeof(mark)); 48 memset(ty,0,sizeof(ty)); 49 for (int i = 0;i <= n * 2;i++) g[i].clear(); 50 } 51 52 bool solve() 53 { 54 for (int i = 0;i < n * 2;i += 2) 55 { 56 if (!mark[i] && !mark[i+1]) 57 { 58 c = 0; 59 60 if (!dfs(i)) 61 { 62 while (c > 0) mark[s[--c]] = 0; 63 if (!dfs(i+1)) return false; 64 else 65 { 66 while (c > 0) mark[s[--c]] = 0; 67 ty[i/2] = 2; 68 } 69 } 70 else 71 { 72 while (c > 0) mark[s[--c]] = 0; 73 if (!dfs(i+1)) 74 { 75 ty[i/2] = 1; 76 while (c > 0) mark[s[--c]] = 0; 77 } 78 else 79 { 80 ty[i/2] = 3; 81 while (c > 0) mark[s[--c]] = 0; 82 } 83 } 84 } 85 else 86 { 87 if (mark[i]) ty[i/2] = 1; 88 else ty[i/2] = 2; 89 } 90 } 91 92 return true; 93 } 94 95 /*void judge() 96 { 97 for (int i = 0;i < n * 2;i += 2) 98 { 99 if (!mark[i] && !mark[i+1]) 100 { 101 c = 0; 102 103 bool tr = 0; 104 bool fa = 0; 105 106 if (dfs(i)) 107 { 108 fa = 1; 109 while (c > 0) mark[s[--c]] = 0; 110 } 111 112 if (dfs(i+1)) 113 { 114 tr = 1; 115 while (c > 0) mark[s[--c]] = 0; 116 } 117 118 if (tr && fa) ty[i/2] = 3; 119 else if (tr) ty[i/2] = 2; 120 else ty[i/2] = 1; 121 } 122 else 123 { 124 //if (i == 0) printf("2333"); 125 if (mark[i]) ty[i/2] = 1; 126 else ty[i/2] = 2; 127 } 128 } 129 }*/ 130 }twosat; 131 132 int main() 133 { 134 int n,m; 135 int kase = 0; 136 137 while (scanf("%d%d",&n,&m) != EOF) 138 { 139 if (n == 0 && m == 0) break; 140 141 twosat.init(n); 142 143 for (int i = 0;i < m;i++) 144 { 145 int k; 146 scanf("%d",&k); 147 148 int a[4]; 149 char ch[4][2]; 150 151 for (int j = 0;j < k;j++) 152 { 153 scanf("%d%s",&a[j],ch[j]); 154 a[j]--; 155 } 156 157 //for (int j = 0;j < k;j++) vis[a[j]] = 1; 158 159 if (k <= 2) 160 { 161 for (int j = 0;j < k;j++) 162 { 163 if (ch[j][0] == 'y') twosat.add_clause(a[j],1,a[j],1); 164 else twosat.add_clause(a[j],0,a[j],0); 165 } 166 } 167 else 168 { 169 bool b[4]; 170 171 for (int j = 0;j < k;j++) 172 { 173 b[j] = ch[j][0] == 'y' ? 1 : 0; 174 } 175 176 for (int j = 0;j < k;j++) 177 { 178 for (int l = 0;l < k;l++) 179 { 180 if (j != l) 181 { 182 twosat.add_clause(a[j],b[j],a[l],b[l]); 183 } 184 } 185 } 186 } 187 } 188 189 if (twosat.solve()) 190 { 191 //twosat.judge(); 192 193 printf("Case %d: ",++kase); 194 195 for (int i = 0;i < n;i++) 196 { 197 switch(twosat.ty[i]) 198 { 199 case 1 : printf("n");break; 200 case 2 : printf("y");break; 201 case 3 : printf("?");break; 202 } 203 } 204 printf(" "); 205 } 206 else printf("Case %d: impossible ",++kase); 207 } 208 209 return 0; 210 }