UVA-11294 Wedding （2-SAT）

题目大意：一张长桌，n对夫妻，编号为0~n，这些人要坐在长桌两侧，每对夫妻不能坐在同一侧。其中，有2*m个人相互讨厌，编号为0的夫妻中的妻子不愿意让对面那一侧中有两个相互吵过架的人，找一种排座位方案。

题目分析：2-SAT问题。如果两个人吵过架，那就一定不能在同一侧，满足“只能取一个”的模型。不过如果dfs(0)失败，就意味着没有解决方案，如果继续dfs(1)，那么找到的方案是“丈夫不愿意看到两个吵过架的人”的排位方案，而不是“妻子”（设2*i表示夫妻中的妻子，2*i+1表示夫妻中的丈夫）。

代码如下：

# include<iostream>

# include<cstdio>

# include<vector>

# include<cstring>

# include<algorithm>

using namespace std;

const int maxn=35;

vector<int>G[2*maxn];

int mark[2*maxn],S[2*maxn],cnt,n,m;

char p[2][3];

void add(int x,int xval,int y,int yval)

{

    x=x*2+xval;

    y=y*2+yval;

    G[x^1].push_back(y);

    G[y^1].push_back(x);

}

bool dfs(int u)

{

    if(mark[u^1])   return false;

    if(mark[u]) return true;

    mark[u]=1;

    S[cnt++]=u;

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

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

            return false;

    return true;

}

bool judge()

{

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

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

            cnt=0;

            if(!dfs(i)){

                if(i==0)    return false;///当新娘在某一侧无解的时候，直接返回false，否则找到的是和新郎同侧的人；

                while(cnt>0)    mark[S[--cnt]]=0;

                if(!dfs(i+1))   return false;

            }

        }

    }

    return true;

}

int main()

{

    int a,b;

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

    {

        for(int i=0;i<2*n;++i)  G[i].clear();

        memset(mark,0,sizeof(mark));

        while(m--)

        {

            scanf("%d%s%d%s",&a,p[0],&b,p[1]);

            int u=0,v=0;

            if(p[0][0]=='h')    u=1;

            if(p[1][0]=='h')    v=1;

            add(a,u,b,v);

        }

        if(!judge())

            printf("bad luck\n");

        else{ for(int i=1;i<n;++i)

            printf("%d%c%c",i,mark[i<<1]?'w':'h',(i==n-1)?'\n':' ');

        }

    }

    return 0;

}

巴特西

UVA-11294 Wedding （2-SAT）

最新文章

热门文章