POJ 3648 Wedding（2-SAT + 輸出方案）

題目連結：Click here~~

題意：

30對夫婦去參加一場婚禮，有一條長桌子，丈夫和妻子不能坐在一側。然後，有些沖突關系，具有那些沖突關系的人不能同時坐在新娘的對面。

輸出坐在新娘這側的人的編号。

解題思路：

搞了3天多的題。搞不出來的時候想死。剛才發現一個 v 打成了i ，呵呵***。

怎麼輸出方案呢？

先對縮點後的圖重建立圖，這裡的圖要逆向建立。

因為原圖 u->v 表示，要選 u 就一定選 v，即選 u 是選 v 的充分條件，但答案不一定選 u 。是以那樣的話，實作還要dfs，複雜度太高。

方法是逆向建圖。然後拓撲排序。将每次得到的點染成紅色，對立的點染成藍色，最後染成紅色的點就是方案中的點。

另外此題雖然要的是坐在新娘這側的編号，但我們求方案時還是要求坐在新娘對面的方案，因為沖突的關系來自對面。

可以添加一條新娘到新郎的邊，防止選新娘到對面。

paint() 函數貌似是沒用的。

#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 1e2+3;
const int M = 2e4+5;

struct Vertex
{
    int head;
}V[N],VV[N];

struct Edge
{
    int v,next;
}E[M],EE[M];

int top,topp,scc,index,dfn[N],low[N],ind[N],belong[N],opp[N];

bool in[N],vis[N],color[N];

stack<int> S;

void init()
{
    top = topp = 0;
    memset(V,-1,sizeof(V));
    memset(VV,-1,sizeof(VV));
}

void add_edge(int u,int v)
{
    E[top].v = v;
    E[top].next = V[u].head;
    V[u].head = top++;
}

void add_edge2(int u,int v)
{
    EE[topp].v = v;
    EE[topp].next = VV[u].head;
    VV[u].head = topp++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++index;
    S.push(u);
    in[u] = true;
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v = E[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        int v;
        do
        {
            v = S.top();
            S.pop();
            in[v] = false;
            belong[v] = scc;
        }while(u != v);
        scc++;
    }
}

void get_scc(int n)
{
    scc = index = 0;
    memset(dfn,0,sizeof(dfn));
    memset(in,false,sizeof(in));
    for(int i=0;i<n;i++)
        if(!dfn[i])
            tarjan(i);
}

bool conflict(int n)
{
    for(int i=0;i<n;i++)
        if(belong[i<<1] == belong[i<<1|1])
            return true;
        else
        {
            opp[ belong[i<<1] ] = belong[i<<1|1];
            opp[ belong[i<<1|1] ] = belong[i<<1];
        }
    return false;
}

void rebuild(int n)
{
    memset(ind,0,sizeof(ind));
    for(int u=0;u<n;u++)
    {
        for(int j=V[u].head;~j;j=E[j].next)
        {
            int v = E[j].v;
            if(belong[u] == belong[v])
                continue;
            ind[belong[u]]++;                   //ni'tu
            add_edge2(belong[v],belong[u]);
        }
    }
}

void paint(int u)
{
    for(int i=VV[u].head;~i;i=EE[i].next)
    {
        int v = EE[i].v;
        if(!vis[v])
        {
            vis[v] = true;
            paint(v);
        }
    }
}

void topSort()
{
    memset(vis,false,sizeof(vis));
    memset(color,false,sizeof(color));
    queue<int> q;
    for(int i=0;i<scc;i++)
        if(!ind[i])
            q.push(i);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        if(vis[u])
            continue;
        vis[u] = true;
        color[u] = true;
        int v = opp[u];
        if(!vis[v])
        {
            vis[v] = true;
            paint(v);
        }
        for(int i=VV[u].head;~i;i=EE[i].next)
        {
            int v = EE[i].v;
            if(--ind[v] == 0)
                q.push(v);
        }
    }
}

int main()
{
    //freopen("in.ads","r",stdin);
    int n,m;
    while(~scanf("%d%d",&n,&m),n||m)
    {
        init();
        while(m--)
        {
            int u,v;
            char c1,c2;
            scanf("%d%c %d%c",&u,&c1,&v,&c2);
            u = c1=='w' ? u<<1 : u<<1|1;
            v = c2=='w' ? v<<1 : v<<1|1;
            add_edge(u,v^1);
            add_edge(v,u^1);
        }
        add_edge(0,1);
        get_scc(n<<1);
        if(conflict(n))
            puts("bad luck");
        else
        {
            rebuild(n<<1);
            topSort();
            for(int i=1;i<n;i++)
                printf("%d%c%c",i,color[ belong[i<<1] ] ? 'h' : 'w',i==n-1?'\n':' ');
        }
    }
    return 0;
}