UVALive

题意：有n个决议和m个人，每个人给至多4个方案投票，问是否存在一种方案使每个人超过一半的投票生效

当一个人投票数小于等于2时，他的每一票都必须生效，否则至多有一票不生效，“至多有一票不生效”等价于“任意两票不能同时不生效”，这样就转化成了一个2-SAT问题

题目还要求输出每一种方案的所有可能，逐一枚举然后2-SAT即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef double db;
 5 const int N=1e5+10;
 6 struct TWO_SAT {
 7     int n,hd[N],ne,col[N],sta[N],tp;
 8     struct E {int v,f,g,nxt;} e[N];
 9     void link(int u,int v,int f,int g) {
10         e[ne]= {v,f,g,hd[u]},hd[u]=ne++;
11         e[ne]= {u,!g,!f,hd[v]},hd[v]=ne++;
12     }
13     void init(int _n) {
14         n=_n,ne=tp=0;
15         for(int i=1; i<=n; ++i)hd[i]=-1;
16     }
17     bool dfs(int u,int c) {
18         if(~col[u])return col[u]==c;
19         col[u]=c,sta[tp++]=u;
20         for(int i=hd[u]; ~i; i=e[i].nxt) {
21             int v=e[i].v,f=e[i].f,g=e[i].g;
22             if(f==col[u]&&!dfs(v,g))return 0;
23         }
24         return 1;
25     }
26     bool check() {
27         for(int i=1; i<=n; ++i)col[i]=-1;
28         for(int i=1; i<=n; ++i)if(!~col[i]) {
29                 tp=0;
30                 if(!dfs(i,0)) {
31                     for(; tp; col[sta[--tp]]=-1);
32                     if(!dfs(i,1))return 0;
33                 }
34             }
35         return 1;
36     }
37 } twosat;
38 struct D {int u; char c;};
39 int ans[N],n,m,ka,hd[N],ne;
40 const char* ss=".ny?";
41 int main() {
42     while(scanf("%d%d",&n,&m),n) {
43         twosat.init(n);
44         while(m--) {
45             vector<D> vec;
46             int k;
47             scanf("%d",&k);
48             for(int i=0; i<k; ++i) {
49                 int u;
50                 char c;
51                 scanf("%d %c",&u,&c);
52                 vec.push_back({u,c});
53             }
54             if(k<=2) {for(D x:vec)twosat.link(x.u,x.u,x.c!='y',x.c=='y');}
55             else {
56                 for(int i=0; i<vec.size(); ++i)
57                     for(int j=i+1; j<vec.size(); ++j)
58                         twosat.link(vec[i].u,vec[j].u,vec[i].c!='y',vec[j].c=='y');
59             }
60         }
61         for(int i=1; i<=n; ++i)hd[i]=twosat.hd[i];
62         ne=twosat.ne;
63         for(int u=1; u<=n; ++u)ans[u]=0;
64         for(int u=1; u<=n; ++u)
65             for(int f=0; f<2; ++f) {
66                 twosat.link(u,u,!f,f);
67                 if(twosat.check())ans[u]|=1<<f;
68                 for(int i=1; i<=n; ++i)twosat.hd[i]=hd[i];
69                 twosat.ne=ne;
70             }
71         bool ok=1;
72         for(int u=1; u<=n; ++u)if(ans[u]==0)ok=0;
73         printf("Case %d: ",++ka);
74         if(!ok)puts("impossible");
75         else {
76             for(int u=1; u<=n; ++u)printf("%c",ss[ans[u]]);
77             puts("");
78         }
79     }
80     return 0;
81 }