poj3648,2-sat求解

关键是题意的理解，英语，有时候明明每个字都认识，但是还是理解错误!哎！！悲剧啊！题意啊！

这是关键！开始误理解为n对新娘郞，非也！是只有一对，其他是夫妇，理解后就好做了，建立图

是关键，怎么转化关系，对到2sat问题上来，不妨设坐在新娘一排的是要“选择”的，那么对每组读入

，必需至少一个要选择，（柳暗花明啦？！）然后标号，2-SAT即可。

没有1A原因：

1：题意到关系一误：特殊情况：当新郞有奸情的时候，与他有奸情的必需选择了（新浪在对面），

当新娘有奸情时候没关系，不处理。

这样后A了。

哎，2-sat问题其实不难啊，这题输出一个解，按以前方法，秒杀之啊！关键还是题意的理解和问题的

转化以及数据的存贮。。。

#include<iostream>  //16MS

#include<cstring>

#include<cstdio>

#include<stack>

#include<vector>

using namespace std;

const int MAX=62;

int n,m;int times=0;

int low[MAX];int dfn[MAX];int visited[MAX];int isinstack[MAX];stack<int>s;

int scc[MAX];int numblock=0;

int ans[MAX];

vector<vector<int> >edges(MAX);  //图

void clear()

{

    times=numblock=0;

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

    {

        ans[i]=visited[i]=dfn[i]=low[i]=isinstack[i];

        scc[i]=-1;

        edges[i].clear();

    }

}

void tarjan(int u)       //dfs

{

    dfn[u]=low[u]=++times;

    isinstack[u]=1;

    s.push(u); int len=edges[u].size();

    for(int i=0;i<len;i++)

       {

           int v=edges[u][i];

           if(visited[v]==0)

           {

               visited[v]=1;

               tarjan(v);

               if(low[u]>low[v])low[u]=low[v];

           }

           else if(isinstack[v]&&dfn[v]<low[u])

              low[u]=dfn[v];

       }

    if(low[u]==dfn[u])

    {

        numblock++;int cur;

        do

        {

            cur=s.top();s.pop();

            isinstack[cur]=0;

            scc[cur]=numblock;

        }while(cur!=u);

    }

}

bool check()           //检查

{

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

         if(visited[i]==0)

         {

             visited[i]=1;

             tarjan(i);

         }

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

    {

        if(scc[i]==scc[i+1])

            return 0;

        if(scc[i]<scc[i+1])

            ans[i/2]=i;

        else ans[i/2]=i+1;

    }

     return 1;

}

void readin()

{

    int temp1;char c1;int temp2;char c2;

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

    {

        scanf("%d%c%d%c",&temp1,&c1,&temp2,&c2);

        if(c1=='h')temp1=2*temp1+1;

        else     temp1=2*temp1;

        if(c2=='h')temp2=2*temp2+1;

        else     temp2=2*temp2;

       if(temp1==1)                //讨论新郞的奸情

       {

           edges[temp2^1].push_back(temp2);

       }

       else if(temp2==1)

       {

           edges[temp1^1].push_back(temp1);

       }

       else if(temp1==0||temp2==0)      //讨论新娘，她有奸情没关系，不影响。

       {

          ;

       }

       else

       {

       edges[temp1^1].push_back(temp2);

       edges[temp2^1].push_back(temp1);

       }

    }

}

int main()

{

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

    {

        clear();

        readin();

        if(check())

        {   int i;

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

            {

                if(ans[i]==i*2)

                printf("%dw ",i);

              else   printf("%dh ",i);

            }

             if(ans[i]==i*2)

                printf("%dw\n",i);

              else   printf("%dh\n",i);

        }

        else

        {

            printf("bad luck\n");

        }

    }

    return 0;

}

巴特西

poj3648,2-sat求解

最新文章

热门文章