uva 11294 (poj 3648 2-SAT)

题意:有若干对夫妇参加婚礼。所有人坐在一张长桌子上妻子和丈夫必须坐在对面,然后给你若干个关系a,b 表示a,b不能做在同一边。问你是否能安排座位,若行输出方案的任意一种。

思路:标准的2-sat的题,套以下lrj的模版然后再判断一下是否有解。

代码如下:

 

uva 11294 (poj 3648 2-SAT)
 1 //2-SAT
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <cstring>
 7 #include <algorithm>
 8 #include <queue>
 9 #include <stack>
10 #include <vector>
11 #define MP(a, b) make_pair(a, b)
12 #define PB(a) push_back(a)
13 
14 using namespace std;
15 
16 typedef long long ll;
17 typedef pair<int ,int> pii;
18 typedef pair<unsigned int, unsigned int> puu;
19 typedef pair<int ,double> pid;
20 typedef pair<ll, int> pli;
21 
22 const int INF = 0x3f3f3f3f;
23 const double eps = 1e-6;
24 const int LEN = 101000;
25 vector<int> Map[LEN];
26 bool mark[LEN*2];
27 int S[LEN*2], c;
28 
29 bool dfs(int x){
30     if(mark[x^1])return false;
31     if(mark[x])return true;
32     mark[x] = true;
33     S[c++] = x;
34     for(int i=0; i<Map[x].size(); i++)
35         if(!dfs(Map[x][i]))return false;
36     return true;
37 }
38 
39 void init(int n){
40     for(int i=0; i<n*2; i++)Map[i].clear();
41     memset(mark, 0, sizeof mark);
42 }
43 
44 void add_clause(int x, int xval, int y, int yval)
45 {
46     x = x*2 + xval;
47     y = y*2 + yval;
48     Map[x^1].PB(y);
49     Map[y^1].PB(x);
50 }
51 
52 bool solve(int n){
53     for(int i=0; i<n*2; i+=2)
54         if(!mark[i] && !mark[i+1]){
55             c = 0;
56             if(!dfs(i)){
57                 while(c>0) mark[S[--c]] = false;
58                 if(!dfs(i+1)) return false;
59             }
60         }
61     return true;
62 }
63 
64 int main()
65 {
66 //    freopen("in.txt", "r", stdin);
67 
68     int x, y, n, m;
69     char a, b;
70     while(scanf("%d%d", &n, &m)!=EOF){
71         if(!n && !m)break;
72         init(n);
73         for(int i=0; i<m; i++){
74             scanf("%d%c%d%c", &x, &a, &y, &b);
75             if(a==w && b==w){ // a v b
76                 add_clause(x,1,y,1);
77             }else if(a==h && b==h){ // !a v !b
78                 add_clause(x,0,y,0);
79             }else if(a==w && b==h){  // a v !b OR !a v b
80                 add_clause(x,1,y,0);
81             }else {
82                 add_clause(x,0,y,1);
83             }
84         }
85         Map[0].PB(1);
86         if(!solve(n)) printf("bad luck\n");
87         else {
88             for(int i=2; i<2*n; i+=2){
89                 if(i!=2) printf(" ");
90                 if(mark[i]==mark[0]) printf("%dw", i/2);
91                 else printf("%dh", i/2);
92             }
93             printf("\n");
94         }
95     }
96     return 0;
97 }
View Code

uva 11294 (poj 3648 2-SAT)

上一篇:Arm学习笔记1——Arm寄存器与模式的关系


下一篇:Photoshop将偏红色的舞台照片校正颜色