本文共 1325 字，大约阅读时间需要 4 分钟。

【题目链接】

【题目大意】

有n-1对夫妇被一对新郎新娘邀请来参加婚礼，他们要坐在一条长桌上，可以选择坐在左边或者右边。每对夫妻都不能坐在同一边，他们只能是面对面坐着。

但是这些人中有JQ，共有m对有JQ（新郎也可能有奸情，可怜的新娘...）。要求这些JQ对不能同时坐在新娘的对面。即，每一对JQ者，他们可以同时坐在和新娘同一边，也可以一个和新娘同一边而另一个在新娘对面即可。

要求找到一种方案并输出，如果没有方案输出bad luck

【思路】

对于每一对夫妇，有两种选择，要么女方和新娘同一边，要么男方和新娘坐在同一边。

然后是根据JQ关系加边。

【代码】

#include
   
     #include
    
     #include
     
      #include
      
       #include
       
        #define WHITE -1#define RED  1#define BLUE 0using namespace std;typedef long long int64;const int MAXN = 50;const int VN = MAXN*2;const int EN = VN*VN;int n, m;struct Edge{    int u, v, next; };struct Graph{    int size, head[VN];    Edge E[EN];    void init(){size=0; memset(head, -1, sizeof(head));};    void addEdge(int u, int v){        E[size].u = u; E[size].v = v;        E[size].next = head[u];        head[u] = size++;    }}g, g1;class Two_Sat{public:    bool check(const Graph&g, const int n){        scc(g, 2*n);        for(int i=0; i