csdn真是神坑,刚写的解题竟然被吞了,尼玛,害我重写。
本题的突破口在每个投票人都要有超过一半的建议被采纳。所以对于k<3的,每个建议都得采纳,k>=3的,只有一个建议不能采纳。
都得采纳的,我用了一个must数组记录,然后dfs找出所有开始就定下来的建议的值;只有一个不能采纳,即每两个建议间都至少有一个被采纳。
最后输出要判断“?”,我的方法是对每个建议检查是否无论它采不采纳都有解。开始忘了dfs找所有应该must的建议,2y
#include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; const int maxn = 100 + 5; struct TwoSAT { int n; vector<int> G[maxn*2]; bool mark[maxn*2],must[maxn*2]; int S[maxn*2], c; bool dfs(int x) { if (mark[x^1]) return false; if (mark[x]) return true; mark[x] = true; S[c++] = x; for (int i = 0; i < G[x].size(); i++) if (!dfs(G[x][i])) return false; return true; } void dfs2(int x){ must[x] = true; for(int i = 0;i < G[x].size();i++) if(!must[G[x][i]]) dfs2(G[x][i]); } void init(int n) { this->n = n; for (int i = 0; i < n*2; i++) G[i].clear(); memset(mark, 0, sizeof(mark)); memset(must,0,sizeof(must)); } void clear(){ memset(mark,0,sizeof(mark)); for(int i = 0;i < 2*n;i++) mark[i] = must[i];//每次都要重新对mark赋值 } // x = xval or y = yval void add_clause(int x, int xval, int y, int yval) { x = x * 2 + xval; y = y * 2 + yval; G[x^1].push_back(y); G[y^1].push_back(x); } bool solve() { for(int i = 0; i < n*2; i += 2){ if(mark[i] && mark[i+1]) return false;//对于开始就有对mark标记的,这句话是必须的 if(!mark[i] && !mark[i+1]) { c = 0; if(!dfs(i)) { while(c > 0) mark[S[--c]] = false; if(!dfs(i+1)) return false; } } } return true; } }; TwoSAT solver; int tag[maxn]; int main(){ int n,m,kase=0; while(scanf("%d%d",&m,&n)){ if(n == 0 && m == 0) break; solver.init(m); memset(tag,0,sizeof(tag)); while(n--){ int c,x[10],valx,valy; char s[10][10]; scanf("%d",&c); for(int i = 0;i < c;i++) scanf("%d%s",&x[i],s[i]); if(c >= 3){ for(int i = 0;i < c;i++) for(int j = i+1;j < c;j++){ valx = s[i][0]=='y'?1:0; valy = s[j][0]=='y'?1:0; solver.add_clause(x[i]-1,valx,x[j]-1,valy); } } else{ for(int i = 0;i < c;i++){ valx = s[i][0]=='y'?1:0; solver.must[2*(x[i]-1)+valx] = 1; } } } for(int i = 0;i < 2*m;i++) if(solver.must[i]) solver.dfs2(i); for(int i = 0;i < m;i++){ if(solver.must[2*i] || solver.must[2*i+1]) continue; solver.clear(); solver.mark[2*i] = true; bool tag1 = solver.solve(); solver.clear(); solver.mark[2*i+1] = true; bool tag2 = solver.solve(); if(tag1 && tag2) tag[i] = 1; } solver.clear(); printf("Case %d: ",++kase); if(!solver.solve()) printf("impossible\n"); else{ for(int i = 0;i < m;i++){ if(tag[i]) printf("?"); else if(solver.mark[2*i]) printf("n"); else printf("y"); } printf("\n"); } } return 0; }