题意:
有N-1对夫妻参加一个婚宴，所有人都坐在一个长长的餐桌左侧或者右侧，新郎和新娘面做面坐在桌子的两侧。由于新娘的头饰很复杂，她无法看到和她坐在同一侧餐桌的人，只能看到对面餐桌的人。任意一对夫妻不能坐在桌子的同侧，另外有m对人吵过架，而新娘不希望看到两个吵过架的人坐在他的对面，问如何安排这些座位。
分析：
考虑新娘对面那一边，吵过架的不能坐在一起。两夫妻中只能选一个而且必须选一个坐在新娘对面，但不能选两个吵过架的人。所以我们可以用人物关系建图，然后用2-SAT求解。
另外，说一下2-SAT的不回溯算法，是在图对称的时候才保证正确性的。所以记得保证图是对称的哦。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 2010
#define Maxm 1000010 int n,m;
int first[Maxn];
bool mark[Maxn];
int s[Maxn],sl; struct node
{
int x,y,next;
}t[Maxm];int len; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} bool dfs(int x)
{
if(mark[x^]) return ;
if(mark[x]) return ;
mark[x]=;
s[++sl]=x;
for(int i=first[x];i;i=t[i].next)
{
if(!dfs(t[i].y)) return ;
}
return ;
} bool ffind()
{
memset(mark,,sizeof(mark));
mark[]=;
if(!dfs()) return ;
for(int i=;i<n;i++)
{
if(mark[i*]||mark[i*+]) continue;
sl=;
if(!dfs(i*))
{
while(sl) mark[s[sl--]]=;
if(!dfs(i*+)) return ;
}
}
return ;
} int main()
{
while()
{
scanf("%d%d",&n,&m);
if(n==&&m==) break;
getchar();len=;
memset(first,,sizeof(first));
bool p;
for(int i=;i<=m;i++)
{
int x,y,p1,p2;
char c;
scanf("%d%c",&x,&c);getchar();
p1=(c=='h'?:);
scanf("%d%c",&y,&c);//getchar();
p2=(c=='h'?:);
getchar();
if(p1==&&p2==) p=;
ins(x*+p1,y*+-p2);//ins(y*2+1-p2,x*2+p1);
ins(y*+p2,x*+-p1);//ins(x*2+1-p1,y*2+p2);
}
if(!ffind()) printf("bad luck\n");
else
{
for(int i=;i<n;i++)
{
if(i!=) printf(" ");
if(mark[i*]) printf("%dw",i);
else printf("%dh",i);
}
}printf("\n");
}
return ;
}
[uva11294]
2016-03-24 13:24:20