2-SAT——7.0（poj3648 Wedding，完結篇）

糾結了這麼久，終于把傳說中的POJ六道 2-SAT 問題（2723，2749，3207，3648，3678，3683）加上 HDU 上面的兩道（3062，3715）全部 A 完，真心糾結啊，建圖真心惡心，有時候真的不知道那些邊該加進去還是不該加進去，說句實話，我覺得 A 完這八題，還是沒有學會 2-SAT，還差的很遠……= =！

今天以這道題做個小結，時間很緊，暫時轉向，待來日再慢慢鑽研……

poj3648 Wedding

題意：有一對新人結婚，邀請 n 對夫婦去參加婚禮，入座時有講究，一個很長的長桌（真心扯淡的題目描述）：

1，每對夫婦不能坐在同一邊；

2，n 對夫婦中有些人之間有暧昧關系（男女，男男，女女都可以……= =！我快囧死了，出題的好重口），如果兩個人有暧昧關系，那麼他倆不能同時坐在新娘對面。

      也就是說，他倆要麼同時和新娘坐在同一邊，要麼差開分别坐在兩邊；

我們根據上面的關系建邊：

用 A 表示丈夫 A 坐左邊，A’ 表示丈夫 A 坐右邊，妻子同理用 B 和 B‘ 表示，然後我們設新娘坐在左邊，

1，根據上面的1有四種邊：（A -> B'），（B -> A'），（A' -> B），（B' -> A）

2，根據上面的2有兩種邊：假如X 和 Y 有暧昧關系，那麼加兩條邊（X' -> Y），（Y' -> X），因為我們設新娘在左邊，是以隻有兩條邊

3，這裡是個容易忽略的地方，新娘和新郎之間也要連邊（詳見代碼），具體為什麼，我也不太懂，還請哪位神牛賜教，orz 個先

#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;

const int N = 2010;

struct Edge{
	int s,e,next;
}edge1[N*N],edge2[N*N];

int n,m,e_num1,vis_num,cnt,head1[N],instack[N],low[N],tim[N],belong[N];
int e_num2,head2[N];
int indeg[2*N],cf[2*N],col[2*N];

void AddEdge1(int a,int b){
	edge1[e_num1].s=a; edge1[e_num1].e=b; edge1[e_num1].next=head1[a]; head1[a]=e_num1++;
}

void AddEdge2(int a,int b){
	edge2[e_num2].s=a; edge2[e_num2].e=b; edge2[e_num2].next=head2[a]; head2[a]=e_num2++;
}

void getmap(){
	int i,a,b;
	char ch1,ch2;
	e_num1=0;
	memset(head1,-1,sizeof(head1));
	
	AddEdge1(1,0);//新娘和新郎加兩條邊,wife' -> wife
	AddEdge1(2,3);//husband -> husband'
	for(i=1;i<n;i++){
		AddEdge1(4*i,4*i+3);
		AddEdge1(4*i+3,4*i);
		
		AddEdge1(4*i+1,4*i+2);
		AddEdge1(4*i+2,4*i+1);
	}
	for(i=0;i<m;i++){
		scanf("%d%c %d%c",&a,&ch1,&b,&ch2);
		a=(ch1=='w')?(4*a):(4*a+2);
		b=(ch2=='w')?(4*b):(4*b+2);
		AddEdge1(a+1,b);
		AddEdge1(b+1,a);
	}
}

stack <int>st;
void tarjan(int x){
    int i;
    tim[x]=low[x]=++vis_num;
    instack[x]=1;
    st.push(x);
    for(i=head1[x];i!=-1;i=edge1[i].next){
        int u=edge1[i].e;
        if(tim[u]==-1){
            tarjan(u);
            if(low[x]>low[u])low[x]=low[u];
        }
        else if(instack[u] && low[x]>tim[u])low[x]=tim[u];
    }
    if(low[x]==tim[x]){
        cnt++;
        do{
            i=st.top();
            st.pop();
            instack[i]=0;
            belong[i]=cnt;
        }while(i!=x);
    }
}

void init(){
	vis_num=cnt=0;
    memset(instack,0,sizeof(instack));
    memset(belong,-1,sizeof(belong));
    memset(tim,-1,sizeof(tim));
    memset(low,0,sizeof(low));
}

void out(){
	int i;

	e_num2=0;
	memset(head2,-1,sizeof(head2));
	memset(indeg,0,sizeof(indeg));
	for(i=0;i<e_num1;i++){
		if(belong[ edge1[i].s ]!=belong[ edge1[i].e ]){
			AddEdge2( belong[ edge1[i].e ], belong[ edge1[i].s ] );//反向邊
			indeg[belong[edge1[i].s]]++;
		}
	}
	
	queue <int>q;
	for(i=1;i<=cnt;i++){
		if(indeg[i]==0)q.push(i);
	}
	
	memset(col,0,sizeof(col));
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		if(col[cur]==0){
			col[cur]=1;
			col[cf[cur]]=-1;
		}
		for(i=head2[cur];i!=-1;i=edge2[i].next){
			int u=edge2[i].e;
			if(--indeg[u]==0)q.push(u);
		}
	}

	int blank=0;
	for(i=1;i<n;i++){
		if(blank==0)blank=1;
		else printf(" ");
		if(col[ belong[4*i+2] ]==1)printf("%dh",i);
		else printf("%dw",i);
	}
	puts("");
}

void solve(){
	int i;
	init();
	for(i=0;i<4*n;i++){
		if(tim[i]==-1)tarjan(i);
	}
	
	int flag=1;
	for(i=0;i<2*n;i++){
		if(belong[2*i]==belong[2*i+1]){
			flag=0;break;
		}
		
		cf[ belong[2*i] ]=belong[2*i+1];
		cf[ belong[2*i+1] ]=belong[2*i];
	}
	if(flag==0) printf("bad luck\n");
	else out();
}

int main()
{
	while(scanf("%d%d",&n,&m),n+m)
	{
		getmap();
		solve();
	}
	return 0;
}