poj 3648 Wedding

本文从WordPress迁移而来, 查看全部WordPress迁移文章

2-sat

题意:新郎和新娘结婚,来了n-1对夫妻,这些夫妻包括新郎之间有通奸关系(包括男女,男男,女女),我们的目地是为了满足新娘,新娘对面不能坐着一对夫妻,也不能坐着有任何通奸关系的人,另外新郎一定要坐新娘对面。但是输出时输出坐在新娘这一边的人(不需要输出新娘)。

很明显的2-sat模型,虽然要输出新娘这一边的人,但是我们构建的是对面的,为什么?因为我们要保证对面的人没有矛盾(但是新娘这一侧是允许有矛盾的,因为新娘看不到她这一侧的人)。另外我们要保证新郎一定坐在对面,在2-sat中固定一个元素的a的方法是~a->a,这个也好理解,a和~a必须选一个,如果选了a那么就选了,如果选了~a,又因为~a->a,说明a也必须选,也就是说无论如何a都要被选到。

按照2-sat正常的流程坐下来,会得到一个可行解,也就是和新郎颜色相同的点,它们都是可行解,它们是没有矛盾的,可以坐在新娘对面,所以剩下的点(其实就是和新娘同色的点)就是和新娘坐在一侧的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define N 2010
#define M 8000010
#define cl memset
#define pb push_back

int n,tot,head[N];
struct edge{
int v,next;
}e[M];
vector<int>ver[N];
vector<int>ans;
queue<int>que;
int dfn[N],low[N],belong[N],stack[N],dcnt,bcnt,top;
bool ins[N];
int inde[N],opp[N],color[N];

inline void add(int u,int v){
e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;
}

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u; ins[u] = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(ins[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u]){
++bcnt;
while(true){
int x = stack[top--];
ins[x] = false;
belong[x] = bcnt;
if(x == u) break;
}
}
}

void scc(){
dcnt = bcnt = top = 0;
cl(dfn,0,sizeof(dfn));
cl(ins,false,sizeof(ins));
for(int i = 0; i < 2*n; i++)
if(!dfn[i])
tarjan(i);
/*
printf("Bcnt = %d\n",bcnt);
for(int i = 0; i <= 2*n; i++)
printf("%d[%d]\n",i,belong[i]);
*/
}

bool check(){
for(int i = 0; i < n ;i++){
if(belong[i<<1] == belong[i<<1|1])
return false;
opp[belong[i<<1]] = belong[i<<1|1];
opp[belong[i<<1|1]] = belong[i<<1];
}
return true;
}

void rebuild(){
for(int i = 1; i <= bcnt; i++){
ver[i].clear(); inde[i] = 0;
}
for(int i = 0; i < 2*n; i++)
for(int k = head[i]; k != -1; k = e[k].next){
int u = belong[i] , v = belong[e[k].v];
if(u == v) continue;
ver[v].pb(u); inde[u]++; //建逆图
}
}

void topsort(){
cl(color,0,sizeof(color));
while(!que.empty()) que.pop();
for(int i = 1; i <= bcnt; i++)
if(inde[i] == 0)
que.push(i);
while(!que.empty()){
int u,v;
u = que.front(); que.pop();
if(!color[u]){
color[u] = 1; color[opp[u]] = 2;
}
for(int i = 0; i < ver[u].size(); i++){
v = ver[u][i]; inde[v]--;
if(inde[v] == 0) que.push(v);
}
}
}

void Find_Ans(){
for(int i = 2; i < 2*n; i++)
if(color[belong[i]] == color[belong[0]]){
printf("%d%c ", i>>1 , (i&1) ? 'h' : 'w');
}
printf("\n");

}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
if(!n && !m) break;
tot = 0;
cl(head,-1,sizeof(head));
while(m--){
int x,y,u,v; char cx,cy;
scanf("%d%c %d%c",&x,&cx,&y,&cy);
u = (x<<1) + (cx == 'h');
v = (y<<1) + (cy == 'h');
add(u,v^1); add(v,u^1);
}
add(0,1); //新郎必选进可行解中
scc();
if(!check()){
puts("bad luck");
continue;
}
rebuild();
topsort();
Find_Ans();
}
return 0;
}