题目链接：https://cn.vjudge.net/contest/209474#problem/C

题目大意：

一共有m个提案，n个政客，每个政客都会对一些提案（最多四个）提出自己的意见——通过或者不通过。一个政客获得满意结果，当且仅当他的意见被满足了超过（注意是超过，即大于）一半，请问有没有这样的方案，使n个政客都满意？如果存在，输出所有方案。（这个所有的意思是一个提案如果只能是“通过”决策（在所有方案里都是通过），输出’y‘，只能不通过输出’n’，可以通过也可以不通过（有的方案是y，有的是n）输出‘?’）

解题思路：

本来想写在《浅谈2-SAT》里，想了想由于这道题比较巧妙，还是单独提出来写。巧妙之处在于1、寻找所有可行方案。2、问题到标准模型的转化。

先谈一下第二点。

一个政客满意，当且仅当他有一半以上的观点被采纳。也就是说，对于只提出一个提案和两个提案的人，只有他提出的所有观点都被采纳，这个人才会满意。对于提出三个提案的人，至少要满足两个观点（最多有一个不满足）；对于提出四个提案的人，至少要满足三个观点（最多有1个不满足）。

每个提案有通过和不通过两种互斥状态，对于观点数量小于等于2的人，他所提出的提案有固定状态（不对称图），对于观点数大于等于3的人，我们如果令其中一个观点为不满足，那么其他的观点都必须满足。

由此我们建立了一个部分确定值的2-SAT图像。

再谈第一点。

这道题的难点其实我自我感觉在第一点。令人惊讶的是，第一点并没有什么高端的处理方法，仅仅是暴力枚举，如果一个提案两种状态的2-SAT图像都成立，那么就是？，只成立一种就是对应结果。如果两种都不成立那么就无解。

下面放有详细注释的9msAC代码并附了几组数据debug（欢迎hack）：

 /* by Lstg */

 /* 2018-03-07 00:33:58 */

 #include<stdio.h>

 #include<iostream>

 #include<vector>

 #include<string.h>

 #define MAXN 5100

 using namespace std;

 vector<int>g[MAXN];

 bool mark[MAXN],f[MAXN];

 int stk[MAXN],top,n,lq[MAXN];

 char ans[];

 int _max(int a,int b){return a>b?a:b;}

 int _abs(int x){return x<?-x:x;}

 void _clean(){

     for(int i=;i<=*n+;i++){

         g[i].clear();

         mark[i]=;

         f[i]=false;

     }

 }

 bool _dfs(int x){

     if(mark[x^])return false;

     if(mark[x])return true;

     mark[x]=true;

     stk[++top]=x;

     for(int i=;i<g[x].size();i++)

         if(!_dfs(g[x][i]))return false;

     return true;

 }

 bool _Twosat(){

     for(int i=;i<=*n+;i+=)

         if(!mark[i]&& !mark[i+]){

             top=;

             if(!_dfs(i)){

                 while(top)

                     mark[stk[top--]]=false;

                 if(!_dfs(i+))return false;

             }

         }

     return true;

 }

 void _addside(int k){

     for(int i=;i<=k;i++)

         for(int j=;j<=k;j++)

             if(j!=i)

                 g[lq[i]^].push_back(lq[j]);//lq[i]^1表示状态的反面，即不满足。在此情况下其他的状态必须满足

 }

 bool _check(){

     int i;

     for(i=;i<=*n+;i++)

         if(f[i]&&!_dfs(i))return false;//如果不能满足固定的状态值就无解

     memcpy(f,mark,sizeof(mark));//f数组已经没用了，用来当过渡

     //printf("n=%d\n",n);

     if(!_Twosat())return false;//如果满足了所有固定状态却不能满足整个2-SAT图，无解

     //puts("haha!\n");

     for(i=;i<=n;i++){

         memcpy(mark,f,sizeof(f));//固定状态都满足的残余2-SAT图作为起始图像

         top=;

         if(!(_dfs(*i)&&_Twosat()))ans[i]='n';/*这里可能有点难理解，我写的确实很绕，没必要跟我一样，

 这里的意思是如果不满足该提案通过，那么这个提案就一定是不通过（因为无解的情况已经全排除了，一定有解，这个提案通过却不满足图像，那么这个提案一定通不过）*/

         else{//如果提案可以通过

             memcpy(mark,f,sizeof(f));

             top=;

             if(_dfs(*i+)&&_Twosat())ans[i]='?';//验证是否也可以不通过

             else ans[i]='y';

         }

     }

     return true;//返回有解

 }

 int main(){

     //freopen("C.txt","w",stdout);

     int m,k,i,j,a,x;

     char ch[];

     int T=;

     while(true){

         scanf("%d%d",&n,&m);

         if(m+n==)return ;

         _clean();

         for(i=;i<=m;i++){

             scanf("%d",&k);

             for(j=;j<=k;j++){

                 scanf("%d%s",&x,ch);

                 a=(ch[]=='y'?:);//2*ii表示通过，2*ii+1表示不通过

                 if(k<=)f[x*+a]=true;//f数组表示有确定状态的提案

                 else lq[j]=x*+a;//lq数组为一会儿构图的媒介

             }

             if(k>=)_addside(k);//用lq数组构图

         }

         printf("Case %d: ",++T);

         if(!_check())printf("impossible\n");

         else{

             for(i=;i<=n;i++)

                 putchar(ans[i]);

             putchar();

         }

     }

     return ;

 }

 /*

 1 1

 1 1 n

 1 1

 1 1 y

 3 2

 3 1 y 2 y 3 n

 3 1 n 2 n 3 y

 3 2

 3 1 y 2 n 3 n

 3 1 n 2 n 3 n

 3 2

 3 1 y 2 y 3 n

 3 1 y 2 n 3 n

 4 2

 4 1 y 2 y 3 n 4 n

 3 2 n 3 n 4 n

 3 2

 3 1 y 2 y 3 n

 3 1 y 2 n 3 n

 */

巴特西

【2-SAT】The Ministers’ Major Mess UVALive – 4452

题目链接：https://cn.vjudge.net/contest/209474#problem/C

最新文章

热门文章