首页 > 其他 > 详细

POJ3648 Wedding

时间:2019-06-19 09:46:54      阅读:138      评论:0      收藏:0      [点我收藏+]

Wedding

Language:
Wedding
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 12576Accepted: 3829Special Judge

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 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 "4h 2w" (husband from couple 4, wife from couple 2), or "10w 4w", or "3h 1h". Couples are numbered from 0 to n - 1 with the bride and groom being 0w and 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 "bad luck".

Sample Input

10 6
3h 7h
5w 3w
7h 6w
8w 3w
7h 3w
2w 5h
0 0

Sample Output

1h 2h 3w 4h 5h 6h 7h 8h 9h

Source

很多对夫妇参加一对新人的婚礼。分别做在长桌子的两侧。新郎、新娘分别坐两侧,新娘只能看到她对面的人。新娘不想看到她对面有夫妇。
而且有一些人是有通奸关系的(男的和男的有,女的和男的、女的和女的都可能有,而且新郎也可能和别人有通奸关系),新娘不想看到有通奸关系一对人。
也就是有通奸关系的不能一起坐在新娘对面。
输入是:n对夫妇(包括新郎新娘在女的,编号为0-(n-1),新郎、新娘那一对的编号为0),m对通奸关系。
接下来m行有通奸关系的。h表示男的,w表是女的,3w 5h即表示第三对夫妇的女的和第五对夫妇的男的有不寻常关系。

题解

我们可以认为一对夫妻是面对面坐的,即每对夫妇是一个节点,然后根据他们的位置与新人的位置相同或相反分为两种对立状态。不用把新郎新娘看成两个节点。

然后m条关系就是标准的2-SAT的关系,跑tarjan按dfn输出方案即可。

求解的时候去选择和新郎同一侧的人,输出的时候换一下就是新娘同一侧的人。
如果i和j有奸情,则增加一条i到j‘,j到i‘的边,
同时增加一条新娘到新郎的边,表示必须选新郎。

本题直接选新娘一边的容易错。因为新娘也可能有奸情,需要排除,具体可以见discuss

#include<iostream>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=201,M=1e5+1;
int n,m,dfn[N],low[N],num;
int head[N],edge[N],next[N],tot;
int c[N],cnt,deg[N],st[N],top;
bool ins[N];

il void add(int x,int y){
    edge[++tot]=y,next[tot]=head[x],head[x]=tot;
}
void tarjan(int x){
    dfn[x]=low[x]=++num;
    st[++top]=x,ins[x]=1;
    for(int i=head[x];i;i=next[i]){
        int y=edge[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        ++cnt;
        int y;
        do{
            y=st[top--],ins[y]=0;
            c[y]=cnt;
        }while(y!=x);
    }
}
void Wedding(){
    tot=num=cnt=0;
    memset(head,0,sizeof head);
    memset(dfn,0,sizeof dfn);
    add(n,0);
    for(int x,cx,y,cy;m--;){
        scanf("%d%c %d%c",&x,&cx,&y,&cy);
        cx=cx=='w',cy=cy=='w';
        add(x+cx*n,y+(cy^1)*n),add(y+cy*n,x+(cx^1)*n);
    }
    for(int i=0;i<n<<1;++i)
        if(!dfn[i]) tarjan(i);
    for(int i=0;i<n;++i)if(c[i]==c[n+i])
        return puts("bad luck"),void();
    for(int i=1;i<n-1;++i) printf("%d%c ",i,c[i]<c[n+i]?'w':'h');
    printf("%d%c\n",n-1,c[n-1]<c[n+n-1]?'w':'h');
}
int main(){
    while(read(n)|read(m)) Wedding();
    return 0;
}

话说这题有人叉了spj……

POJ3648 Wedding

原文:https://www.cnblogs.com/autoint/p/11049480.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!