poj3648 2-sat

个人不可以同时坐在新娘对面。

     根据限制关系，而且还是二选一，显然这个是2sat,对于每个人，都拆成两个点，一个是a表示坐在新娘这一侧，另一个是~a表示坐在新郎这一侧，则对于任何有暧昧关系的，要么一边坐一个，要不同时坐在新娘这一侧，则只要他们两个中至少有一个1就行了，建图是这样 ~a -> b ,~b -> a,对于每一对，他们不能坐在同一侧则不能相同，建图是 a -> ~b ,b -> ~a ,~a ->b ,~b -> a ,还有就是新娘必须坐在新娘这侧，直接 ~a -> a.

#include<stdio.h>
#include<string.h>
#include<stack>

#define N_node 5000
#define N_edge 100000
#define R 1
#define B 2

using namespace std;

typedef struct
{
   int to ,next;
}STAR;

STAR E1[N_edge] ,E2[N_edge];
int list1[N_node] ,list2[N_node] ,tot;
int Belong[N_node] ,cnt;
int mark[N_node] ,Col[N_node];
stack<int>st ,stt;

void add(int a ,int b)
{
   E1[++tot].to = b;
   E1[tot].next = list1[a];
   list1[a] = tot;
   
   E2[tot].to = a;
   E2[tot].next = list2[b];
   list2[b] = tot;
}

void DFS1(int s)
{
    mark[s] = 1;
    for(int k = list1[s] ;k ;k = E1[k].next)
    if(!mark[E1[k].to]) DFS1(E1[k].to);
    st.push(s) ,stt.push(s);
}

void DFS2(int s)
{
     mark[s] = 1;
     Belong[s] = cnt;
     for(int k = list2[s] ;k ;k = E2[k].next)
     if(!mark[E2[k].to]) DFS2(E2[k].to);
}

bool solve(int n)
{
     memset(mark ,0 ,sizeof(mark));
     while(!st.empty()) st.pop();
     while(!stt.empty()) stt.pop();
     for(int i = 0 ;i < 4 * n ;i ++)
     if(!mark[i]) DFS1(i);
     memset(mark ,0 ,sizeof(mark)) ,cnt = 0;
     while(!st.empty())
     {
        int xin = st.top();
        st.pop();
        if(mark[xin]) continue;
        cnt ++;
        DFS2(xin);
     }
     for(int i = 0 ;i < n * 4 ;i += 2)
     if(Belong[i] == Belong[i^1]) return 0;
     return 1;
}

int main ()
{
    int i ,n ,m ,a ,b;
    char c1 ,c2;
    while(~scanf("%d %d" ,&n ,&m) && n + m)
    {
        memset(list1 ,0 ,sizeof(list1));
        memset(list2 ,0 ,sizeof(list2)) ,tot = 1;
        for(i = 1 ;i <= m ;i ++)
        {
           scanf("%d%c%d%c" ,&a ,&c1 ,&b ,&c2);
           a = a * 2 + (c1 == 'h' ? 1 : 0);
           b = b * 2 + (c2 == 'h' ? 1 : 0);
           add(a * 2 + 1 ,b * 2);
           add(b * 2 + 1 ,a * 2);
        } 
        for(i = 0 ;i < n ;i ++)
        {
           a = i * 2 ,b = i * 2 + 1;
           add(a * 2 + 1 ,b * 2) ,add(b * 2 + 1 ,a * 2);
           add(a * 2 ,b * 2 + 1) ,add(b * 2 ,a * 2 + 1);
        }
        add(1 ,0);
        if(!solve(n))
        {
            printf("bad luck
");
            continue;
        }
        memset(Col ,0 ,sizeof(Col));
        while(!stt.empty())
        {
           i = stt.top() ,stt.pop();
           if(Col[i]) continue;
           Col[i] = B ,Col[i^1] = R;
        }
        int mk = 0;
        for(i = 4 ;i < n * 4 ;i += 2)
        {       
            if(Col[i] == B) continue;
            if(mk) printf(" ");mk = 1;
            printf("%d" ,i / 4);
            i % 4 > 1 ? printf("h") : printf("w");
        }
        puts("");
    }
    return 0;
}