欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

POJ 3648 Wedding(2

程序员文章站 2022-05-30 15:42:24
...

POJ 3648 Wedding(2-SAT) http://poj.org/problem?id=3648 题意: 有一对新人结婚,n-1对夫妇去参加婚.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时

POJ 3648 Wedding(2-SAT)

http://poj.org/problem?id=3648

题意:

有一对新人结婚,n-1对夫妇去参加婚礼.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时坐在新娘对面.(只能分开做,或者都坐到新娘一边去)。对于每个输入实例,输出应该坐在新娘同一边的人编号。

分析:

由于有n对夫妇(0号表示新婚夫妻).所以我们这里用0表示第0对的妻子,1表示第0对的丈夫. 2*i表示第i对的夫人,2*i+1表示第i对的丈夫.一共就有2*n个人了.

然后对于每个人来说,把他分成两个节点,如果该人在做左边就mark[i*2],如果该人坐右边就mark[i*2+1].

我令新娘直接坐左边即第0个人mark[0]=true,新郎直接坐右边即第1个人mark[1*2+1]=true.

然后对于每对夫妻,因为他们不能在同一边,所以第i对夫妻中a= 2*i表示妻子,b=2*i+1表丈夫. 有这样的关系:

a在左边,那么b就在右边,a*2->b*2+1

a在右边,那么b就在左边,a*2+1->b*2

b在左边,那么a就在右边,b*2->a*2+1

b在右边,那么a就在左边,b*2+1->a*2

然后对于每对有奸情的人a与b,因为它们不能同时在新娘对面(右边),所以:

a*2+1->b*2

b*2+1->a*2

注意首先我们定了新娘(0号)在左边,新郎(第1号人)一定在右边,所以我们要先加上:

0*2+1->0*2 和 1*2->1*2+1

这样就保证了新娘和新郎在固定的那边不动.

AC代码:

#include
#include
#include
#include
using namespace std;
const int maxn = 1000*2+100;
struct TwoSAT
{
    int n;
    vector G[maxn*2];
    int S[maxn*2],c;
    bool mark[maxn*2];

    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;in=n;
        for(int i=0;i0) mark[S[--c]]=false;
                if(!dfs(i+1)) return false;  //注意细节,这里写成了return true;
            }
        }
        return true;
    }
}TS;
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        if(n==0&&m==0) break;
        TS.init(n*2);
        TS.add_clause(0,1,0,0);//新娘放左
        TS.add_clause(1,0,1,1);//新郎放右
        for(int i=1;i