Wedding（2-SAT）

传送门

稍微复杂一点的2-SAT。

读题之后发现有以下限制：

1.每一对夫妻（包括新郎和新娘）不能坐在桌子的一侧。

2.对于一些给定的非法（自行脑补）的关系，这两个人不能坐在新娘的同一侧。

因为每个人只有两种就坐方式，所以每个人可以被看成一个布尔变量。我们把每一对夫妻拆成两个点，分别表示是否坐在新郎的一侧。这样只要夫妻直接不连边，就不会坐在一起，然后把非法关系的两个人，每个人向对方的否定去连边，因为如果一个人坐在一边，另一个人不可以坐在这边，那么他的否定必然要坐在这边。

注意新娘的对面是必须有新郎的。把新娘向新郎连一条边，这样相当于是自己向自己的否定连边，那么结果为假，也就是新郎坐在了新郎那一侧。这样之后我们跑2-SAT即可。

不过注意一下，因为我们设定的是是否坐在新郎的一侧，我们要求的是是否坐在新娘的一侧，所以最后在判断的时候判断的条件要反过来。

看一下代码。（感觉此题有点奇怪难懂？）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')

using namespace std;
typedef long long ll;
const int M = 1005;
const int INF = 1000000009;

int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct edge
{
    int next,from,to;
}e[M<<1];

int n,m,head[M],cnt,scc[M],dfn[M],low[M],idx,ecnt,a,b,stack[M],top;
char c,d;
bool vis[M],flag;

int rev(int x)
{
    return x > n ? x - n : x + n;
}

void clear()
{
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
    memset(scc,0,sizeof(scc));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    ecnt = cnt = idx = 0;
}

void add(int x,int y)
{
    e[++ecnt].to = y;
    e[ecnt].from = x;
    e[ecnt].next = head[x];
    head[x] = ecnt;
}

void build()
{
    rep(i,1,m)
    {
    scanf("%d%c %d%c",&a,&c,&b,&d);
    a++,b++;
    if(c == 'h') a += n;
    if(d == 'h') b += n;
    add(a,rev(b)),add(b,rev(a));
    }
    add(1,1+n);
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++idx;
    stack[++top] = x,vis[x] = 1;
    for(int i = head[x];i;i = e[i].next)
    {
    if(!dfn[e[i].to]) tarjan(e[i].to),low[x] = min(low[x],low[e[i].to]);
    else if(vis[e[i].to]) low[x] = min(low[x],dfn[e[i].to]);
    }
    if(low[x] == dfn[x])
    {
    int p;
    cnt++;
    while(p = stack[top--])
    {
        scc[p] = cnt,vis[p] = 0;
        if(p == x) break;
    }
    }
}

int main()
{
    while(1)
    {
    n = read(),m = read();
    if(!n && !m) break;
    clear(),build();
    rep(i,1,n<<1) if(!dfn[i]) tarjan(i);
    flag = 1;
    rep(i,1,n)
    {
        if(scc[i] == scc[i+n])
        {
        flag = 0;
        break;
        }
    }
    if(!flag) printf("bad luck
");
    else
    {
        rep(i,2,n)
        {
        if(scc[i] > scc[i+n]) printf("%d%c ",i-1,'w');
        else printf("%d%c ",i-1,'h');
        }
        enter;
    }
    }
    return 0;
}