Wedding UVA

题意：

有N-1对夫妻参加一个婚宴，所有人都坐在一个长长的餐桌左侧或者右侧，新郎和新娘面做面坐在桌子的两侧。由于新娘的头饰很复杂，她无法看到和她坐在同一侧餐桌的人，只能看到对面餐桌的人。任意一对夫妻不能坐在桌子的同侧，另外有m对人吵过架，而新娘不希望看到两个吵过架的人同时坐在他的对面，问如何安排这些座位

解析：

  原本我想的是 把每个人分别拆点  左右分别是 2*i  和 2*i+1  但。。仔细想一下 妻子和丈夫不能坐在同一边  而且一对夫妻的编号也是一样的  不如就把夫妻两人分别作为 2*i 和 2*i+1  

这里设 妻子为2*i  丈夫 为2*i+1

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(a, n) for(int i=a; i<=n; i++)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _  ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 10010, INF = 0x7fffffff;
int n, m;


struct twosat
{
    int n;
    vector<int> G[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2], c;

    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; i<G[x].size(); i++)
            if(!dfs(G[x][i])) return false;
        return true;
    }

    void init(int n)
    {
        this->n = n;
        for(int i=0; i<n*2; i++) G[i].clear();
        mem(mark, 0);
        mark[0] = 1;   //0是新娘 标记
    }

    void add_clause(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 solve()
    {
        for(int i=0; i<n*2; i+=2)
            if(!mark[i] && !mark[i+1])
            {
                c = 0;
                if(!dfs(i))
                {
                    while(c > 0) mark[S[--c]] = false;
                    if(!dfs(i+1)) return false;
                }
            }
        return true;
    }
};

twosat solver;


int main()
{
    while(~scanf("%d%d", &n, &m) && n+m)
    {
        solver.init(n);
        int x, y;
        char a, b;
        for(int i=0; i<m; i++)
        {
            scanf("%d%c %d%c", &x, &a, &y, &b);
            int xval = (a=='w')?0:1;
            int yval = (b=='w')?0:1;
            solver.add_clause(x, xval, y, yval);   //x与y不能同在一侧
        }

        if(!solver.solve())
        {
            printf("bad luck
");
            continue;
        }
        for(int i=1; i<n; i++)   //0是新娘
        {
            if(i!=1)
                printf(" ");
            printf("%d%c", i,solver.mark[i*2]?'w':'h');
        }
        printf("
");

    }


    return 0;
}