UVALive 4452 The Ministers' Major Mess（2-sat）

2-sat。又学到了一种使用的方法：当确定选择某中状态A时，从它的对立状态A^1引一条边add(A^1,A)，从而使凡是dfs经过对立状态，必然return false；即保证若存在一种可能性，必然是经过该状态A的。

题意：m个人对n个方案投票，每人之多投4票，是否存在一种方案使每个人所投的一半以上的票被采纳。依次输出每个议题最终的结果。

1、注意是一半以上，我一开始理解成一半，结果无法根据必然性建边。<=2票则都被采纳，<=4票则至多有一票不被采纳。

2、输出时要注意，因为每个议题的结果都不一定相同，所以需要一一判断。需要分别进行solve（i），和solve（i+1）。这里一开始我直接是把solve（）函数中的dfs(i)和dfs(i+1)分开，wa了，后来考虑发现，solve（）一次，是对遍历整个方案寻找可行性；而dfs（）只是对一个连通的量做了标记。

注意：分别检查同一个议题的两种状态，确定从状态A经过，add(A^1,A)，结束要记得G[i].pop_back();

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 struct Vote{

     int v,c;

 }vote[MAXN][];

 bool mark[MAXN<<];

 int res[MAXN];

 int s[MAXN<<],c;

 vector<int >G[MAXN<<];

 void init(int n)

 {

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

         G[i].clear();

     memset(mark,,sizeof(mark));

 }

 void add(int x,int dx,int y,int dy)

 {

     x=(x<<)+dx;

     y=(y<<)+dy;

     G[x].push_back(y);

 }

 bool dfs(int x)

 {

     if(mark[x^])

         return false;

     if(mark[x])

         return true;

     s[c++]=x;

     mark[x]=true;

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

         if(!dfs(G[x][i]))

             return false;

     return true;

 }

 bool solve(int n)

 {

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

     {

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

             c=;

             if(!dfs(i)){

                 while(c>)

                     mark[s[--c]]=false;

                 if(!dfs(i+))

                     return false;

             }

         }

     }

     return true;

 }

 bool test(int n)

 {

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

     {

         int ans=;

         memset(mark,,sizeof(mark));

         add(i,,i,);

         while(c>)

             mark[s[--c]]=false;

         if(solve(n))

             ans+=;

         G[(i<<)+].pop_back();

         memset(mark,,sizeof(mark));

         add(i,,i,);

         while(c>)

             mark[s[--c]]=false;

         if(solve(n))

             ans+=;

         G[i*].pop_back();

         if(ans==)

             return false;

         else if(ans==)

             res[i]=-;

         else if(ans==)

             res[i]=;

         else if(ans==)

             res[i]=;

     }

     return true;

 }

 int main()

 {

     int n,m;

     int cnt=,ans;

     while(~scanf("%d%d",&n,&m))

     {

         if(!n&&!m)

             return ;

         init(n);         //!!

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

         {

             scanf("%d",&ans);

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

             {

                 int x;

                 char ch[];

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

                 vote[i][j].v=--x;

                 if(ch[]=='y')

                     vote[i][j].c=;

                 else

                     vote[i][j].c=;

             }

             if(ans<=){

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

                     add(vote[i][j].v,vote[i][j].c^,vote[i][j].v,vote[i][j].c);

             }else

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

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

                     {

                         if(j==k)

                             continue;

                         add(vote[i][j].v,vote[i][j].c^,vote[i][k].v,vote[i][k].c);

                     }

         }

         memset(res,,sizeof(res));

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

         if(!test(n))

             printf("impossible\n");

         else {

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

             {

                 if(res[i]==)

                     printf("?");

                 else if(res[i]==)

                     printf("y");

                 else if(res[i]==-)

                     printf("n");

             }

             printf("\n");

         }

     }

     return ;

 }

 /*

 5 3

 2 1 y 2 n

 3 1 y 3 n 4 y

 4 1 n 3 n 4 n 5 y

 */

巴特西

UVALive 4452 The Ministers' Major Mess（2-sat）

最新文章

热门文章