poj 六道2-sat第四题：

题目描述：

一堆夫妇去参加一对新人的婚礼。人们坐在一个很长很长的桌子的两侧（面对面）。新郎新娘在桌子头面对面座。

新娘不希望看见她对面的一排有一对夫妇坐着（夫妇需要分开两排座）。

同时，一些人之间有暧昧关系，新娘也不希望有暧昧关系的人同时坐在她对面的一排。

问你可否满足新娘的要求，可以的话，输出一种方案。

解题报告：

首先，每个人都可能坐在桌子两侧的某一侧，这样，把每个人拆成两个点。

第一个点表示桌子左侧（我自己定义的），第二个表示右侧。即i和i’

新娘我让她坐在左侧，新郎坐在右侧。

新娘编号0，加入边i’-》i，就是说如果新娘坐右侧的话，就需要坐到左侧（这样就限定了新娘坐在左侧），新郎同样处理。

夫妇一定一左侧，一右侧。

有暧昧关系的人要么同时坐在左侧（不让新娘看见），要么一个坐在左侧，一个坐在右侧。

这样图就建好了。

剩下的就是套用2-sat算法了。

代码如下：

#include<iostream>
using namespace std;
#define size 200 // 点的个数
#define esize 10000 // 边的个数
int v[size], cnt, v2[size], cnt2;
struct edge{int from, to, next;}e[esize], e2[esize];
void insert(int from, int to)
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].next = v[from]; v[from] = cnt++;
}
void insert2(int from, int to)
{
    e2[cnt2].from = from, e2[cnt2].to = to; e2[cnt2].next = v2[from]; v2[from] = cnt2++;
}
int index, dfn[size], low[size], instack[size], sta[size], top;
int belong[size], cntnum, num[size];
int cf[size], rd[size], que[size], col[size];
bool ans[size];//1表示选择
void tarjan(int id)
{
    dfn[id] = low[id] = ++index;
    instack[id] = 1; sta[top++] = id;
    int tmp = v[id];
    while(tmp != -1)
    {
        if (!dfn[e[tmp].to])
        { tarjan(e[tmp].to);
            if (low[e[tmp].to] < low[id]) low[id] = low[e[tmp].to];
        }
        else if (instack[e[tmp].to] && dfn[e[tmp].to] < low[id])
            low[id] = dfn[e[tmp].to];
        tmp = e[tmp].next;
    }
    if (dfn[id] == low[id])
    {
        do
        { tmp = sta[--top]; instack[tmp] = 0;
            belong[tmp] = cntnum;
            num[cntnum]++;
        }while(tmp != id);
        cntnum++;
    }
}
bool solve(int n) // n是一半的点数(实际的人数) 执行tarjan和topsort,完成标记
{
    index = cntnum = top = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(num, 0, sizeof(num));
    for(int i = 0; i < 2 * n; i++)
        if (!dfn[i]) tarjan(i);
    for(int i = 0; i < n; i++)                  //在缩点的图中标记互斥的缩点。（原来互斥，现在也互斥）
    {
        if (belong[i] == belong[i + n])
        {
            //cout << i + 1 << "haha" << endl;
            return false;
        }
        cf[belong[i]] = belong[i + n];
        cf[belong[i + n]] = belong[i];
    }
    memset(rd, 0, sizeof(rd));
    memset(v2, -1, sizeof(v2));
    memset(col, 0, sizeof(col));cnt2 = 0;
    for(int i = 0; i < cnt; i++)      //建立缩点图，边用的是反向边，同时统计入度。
        if (belong[e[i].from] != belong[e[i].to])
        {
            insert2(belong[e[i].to], belong[e[i].from]);
            rd[belong[e[i].from]]++;
        }
    int head = 0, tail = 0;                //开始topsort
    for(int i = 0; i < cntnum; i++)
        if (rd[i] == 0) que[tail++] = i;
    while(head < tail)
    {
        int tmp = que[head++];
        if (col[tmp] == 0)                   //对于未着色的点x，将x染成红色，同时将与x矛盾的点cf[x]染成蓝色。
        {
            col[tmp] = 1;
            col[cf[tmp]] = -1;
        }
        int id = v2[tmp];
        while(id != -1)
        {
            if (--rd[e2[id].to] == 0)
                que[tail++] = e2[id].to;
            id = e2[id].next;
        }
    }
    memset(ans, 0, sizeof(ans));
    for(int i = 0; i < 2 * n; i++) // 2-sat的一组解就等价于所有缩点后点颜色为红色的点
        if (col[belong[i]] == 1) ans[i] = 1;
    return true;
}
int n, m;
char str[2][20];
int judge(int id)
{
    int len = strlen(str[id]), num = 0;
    for(int i = 0; i < len - 1; i++)
    {
        num *= 10;
        num += str[id][i] - '0';
    }
    if (str[id][len - 1] == 'h') return num;
    else return (num + n / 2);
}
void judge2(int xx)
{
    char c = 'h';
    if (xx >= n / 2) {xx -= (n / 2); c = 'w';}
    printf("%d%c", xx, c);
}
int main()
{
    while(scanf("%d%d", &n ,&m) && (n || m))
    {
        memset(v, -1, sizeof(v)); cnt = 0;
        for(int i = 1; i < n; i++)
        {
            insert(i, i + n + n + n);
            insert(i + n + n, i + n);
            insert(i + n, i +  n + n);
            insert(i + n + n + n, i);
        }
        insert(n + n + n, n);
        insert(0, n + n);
        n *= 2;

        for(int i = 0; i < m; i++)
        {
            scanf("%s%s", str[0], str[1]);
            int a = judge(0), b = judge(1);
            insert(a + n, b);
            insert(b + n, a);
        }
        if (solve(n))
        {
            int cnt = 0;
            for(int i = 1; i < n; i++)
            {
                if (ans[i] && i != n / 2)
                {
                    judge2(i);
                    cnt++;
                    if (cnt == n / 2 - 1) printf("\n");
                    else printf(" ");
                }
            }
        }
        else printf("bad luck\n");
    }
    return 0;
}