POJ 3648/UVA 11294 Wedding 题解 【2-SAT】【tarjan】
点击量：212
需要先读懂题……然后套上2-SAT，还得注意细节。
Description
Up to thirty couples will attend a wedding feast, at which they will be seated on either side of a long table.
The bride and groom sit at one end, opposite each other, and the bride wears an elaborate headdress that keeps her from seeing people on the same side as her. It is considered bad luck to have a husband and wife seated on the same side of the table. Additionally, there are several pairs of people conducting adulterous relationships (both different-sex and same-sex relationships are possible), and it is bad luck for the bride to see both members of such a pair. Your job is to arrange people at the table so as to avoid any bad luck.
Input
The input consists of a number of test cases, followed by a line containing ‘\(\tt 0\ 0\)’. Each test case gives \(n\), the number of couples, followed by the number of adulterous pairs, followed by the pairs, in the form ‘\(\tt 4h\ 2w\)’ (husband from couple \(4\), wife from couple \(2\)), or ‘\(\tt 10w\ 4w\)’, or ‘\(\tt 3h\ 1h\)’. Couples are numbered from \(0\) to \(n-1\) with the bride and groom being ‘\(\tt 0w\)’ and ‘\(\tt 0h\)’.
Output
For each case, output a single line containing a list of the people that should be seated on the same side as the bride. If there are several solutions, any one will do. If there is no solution, output a line containing ‘\(\tt bad luck\)’.
Sample Input
10 6 3h 7h 5w 3w 7h 6w 8w 3w 7h 3w 2w 5h 0 0Sample Output
1h 2h 3w 4h 5h 6h 7h 8h 9h
题意：
有一对新郎和新娘邀请了\(n-1(n\le 30)\)对夫妇来参加他们的婚礼，每对夫妇的其中一个坐在新娘这边，另一个坐在新郎那边。但是不幸的是这\(30\)对夫妇之间有通奸现象，好在新娘披着盖头，看不见她同侧的情况。需要找出一种座位安排方案，使得新娘的对面没有任何一对通奸的人，并输出坐在新娘这边的人。
题解：
一开始把题读错了，以为有\(30\)对新人结婚……实际上新娘(bride)只有一个。因此输入数据中的一对不能同时坐在新娘的对面，这时可以用2-SAT来解决问题。
首先拆点，况且本来就是丈夫和妻子两个人。令妻子‘\(\tt w\)’坐在新娘同侧为\(x_0\)，丈夫‘\(\tt h\)’坐在新娘同侧为\(x_1\)。如果输入\(x\mathtt w,y\mathtt w\)，则当\(x_1\)坐在新娘这边时，\(y_0\)就必须也坐在新娘这边，因为\(x_0\)已经在对面了；同理当\(y_1\)坐在新娘这边时\(x_0\)就必须坐在新娘这边。还有3种情况大致是一样的。连了这样的有向边，接着我们就可以来做tarjan辅助拓扑排序了。
本题大致这里就结束了。但是除了\(x_0,x_1\)在同一强连通分量外，还有一种要输出‘\(\tt bad\ luck\)’的情况，就是从\(0\tt w\)出去沿着有向边可以找到\(0\tt h\)，这样的话表示选择\(0\tt w\)就得选择\(0\tt h\)坐在新娘同侧。但是要求一对夫妇必须坐在对面，因此这样是不成立的，只需要一开始跑一遍tarjan判断有没有跑到\(0\tt h\)即可。注意这个题从\(0\)开始编号，那么总编号就是\(\{0,1,\dots ,2n-1\}\)，开够数组大小即可。
Code：
#include<cstdio>
#include<cstring>
struct edge
{
int n,nxt;
edge(int n,int nxt)
{
this->n=n;
this->nxt=nxt;
}
edge(){}
}e[100];
int head[100],ecnt=-1;
void add(int from,int to)
{
e[++ecnt]=edge(to,head[from]);
head[from]=ecnt;
}
void read(int &x,int &y)
{
char ch=getchar();
x=0;
while(ch<'0'||ch>'9')
{
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
y=(ch=='h');
}
int dfn[100],low[100],del[100],cnt=0;
int dcnt=0,stk[100],tp=0;
bool in[100];
void tarjan(int x,int from)
{
dfn[x]=++cnt;
low[x]=dfn[x];
stk[++tp]=x;
in[x]=1;
for(int i=head[x];~i;i=e[i].nxt)
if(e[i].n!=from)
{
if(!dfn[e[i].n])
{
tarjan(e[i].n,x);
low[x]=low[x]<low[e[i].n]?low[x]:low[e[i].n];
}
else if(in[e[i].n])
low[x]=low[x]<dfn[e[i].n]?low[x]:dfn[e[i].n];
}
if(low[x]==dfn[x])
{
++dcnt;
do
{
del[stk[tp]]=dcnt;
in[stk[tp--]]=0;
}while(stk[tp+1]!=x);
}
return;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
while(n)
{
memset(head,-1,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(del,0,sizeof(del));
ecnt=-1;
dcnt=0;
cnt=0;
int u,v,w,x;
for(int i=1;i<=m;++i)
{
read(u,v);
read(w,x);
if(v==0&&x==0)
{
add(u+n,w);
add(w+n,u);
}
else if(v==0&&x==1)
{
add(u+n,w+n);
add(w,u);
}
else if(v==1&&x==0)
{
add(u,w);
add(w+n,u+n);
}
else
{
add(u,w+n);
add(w,u+n);
}
}
tarjan(0,0);
if(del[n])
{
puts("bad luck");
scanf("%d%d",&n,&m);
continue;
}
int flag=0;
for(int i=1;i<=2*n-1;++i)
{
if(!dfn[i])
tarjan(i,i);
if(i>=n&&del[i]==del[i-n])
{
flag=1;
break;
}
}
if(flag)
{
puts("bad luck");
scanf("%d%d",&n,&m);
continue;
}
for(int i=1;i<n;++i)
if(del[i]<del[i+n])
printf("%dw ",i);
else
printf("%dh ",i);
scanf("%d%d",&n,&m);
}
return 0;
}
… [Trackback]
[…] Read More here on that Topic: wjyyy.top/2781.html […]