现在的位置: 首页 > 综合 > 正文

2-SAT——7.0(poj3648 Wedding,完结篇)

2014年01月31日 ⁄ 综合 ⁄ 共 2873字 ⁄ 字号 评论关闭

纠结了这么久,终于把传说中的POJ六道 2-SAT 问题272327493207,3648,36783683)加上
HDU 上面的两道(30623715)全部 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;
}

抱歉!评论已关闭.