2-Sat小结

关于2-sat，其实就是一些对于每个问题只有两种解，一般会给出问题间的关系，比如and，or，not等关系，判定是否存在解的问题。。

具体看http://blog.csdn.net/jarjingx/article/details/8521690，该博客写得很不错的。

下面是LRJ白书上给的2-sat，个人觉得写的很不错。。效率也很高。

 1 #define maxn 500
 2 struct TwoSat{
 3      int n;
 4      vector<int> G[maxn * 2];
 5      bool mark[maxn * 2];
 6      int S[maxn * 2], c;
 7      bool dfs(int x){ // 搜索一组解 
 8           if (mark[x^1]) return false; //出现冲突 
 9           if (mark[x]) return true;
10           mark[x] = true;
11           S[c++] = x;
12           for (int i = 0; i < G[x].size(); ++i)
13               if (!dfs(G[x][i])) return false;
14           return true;
15      }
16 
17      void init(int n){
18           this->n = n;
19           for (int i = 0; i < 2 * n; ++i)
20               G[i].clear();
21           memset(mark, 0, sizeof(mark));
22      }
23 
24      void add_clause(int x, int xv, int y, int yv){
25            x = x * 2 + xv;
26            y = y * 2 + yv; //x,y不能同时存在，那么如果选了y，合法解必定要选x^1
27            G[x].push_back(y^1); 
28            G[y].push_back(x^1); 
29      }
30 
31      bool solve(){
32            for (int i = 0; i < n * 2; i += 2)
33                if (!mark[i] && !mark[i+1]){
34                     c = 0;
35                     if (!dfs(i)){ //枚举2种取值都无解 
36                           while (c > 0) mark[S[--c]] = false;
37                           if (!dfs(i+1)) return false;
38                     }
39                }
40            return true;
41      }
42 };

下面是poj上经典2-sat题目：

Poj2296：http://www.cnblogs.com/yzcstc/p/3588099.html

PoJ2723：

题意：

有m道门,每到门上有两把锁,打开其中的一把锁就能打开这道门,有2n把不同的钥匙,每把对应一种锁,这些钥匙被分成n对,每队钥匙只能取其中的一把,取了一把之后另一把就会消失,然后给出每一道门对应的钥匙,求解能打开的门的最大数量.注意，必须打开这一道门才能通往下一个门

思路：

二分一下答案，那么就转化为判定问题。接下去就是2-sat问题了

对于同一对钥匙a和b，属于互斥关系，添加a->~b, b->~a边

对于同一个门的两个钥匙，属于or的关系，即~a与~b互斥，添加~a->b, ~b->a的边

Code：

  1 /*
  2  * Author:  Yzcstc
  3  * Created Time:  2014/3/8 17:14:52
  4  * File Name: Poj2723.cpp
  5  */
  6 #include<cstdio>
  7 #include<iostream>
  8 #include<cstring>
  9 #include<cstdlib>
 10 #include<cmath>
 11 #include<algorithm>
 12 #include<string>
 13 #include<map>
 14 #include<set>
 15 #include<vector>
 16 #include<queue>
 17 #include<stack>
 18 #include<ctime>
 19 #define M0(x) memset(x, 0, sizeof(x))
 20 #define rep(i, a, b) for (int i = (a); i <= (b); ++i)
 21 #define red(i, a, b) for (int i = (a); i >= (b); --i)
 22 #define PB push_back
 23 #define Inf 0x3fffffff
 24 #define eps 1e-8
 25 typedef long long LL;
 26 using namespace std;
 27 #define maxn 40000
 28 int p[maxn];
 29 int X[maxn], Y[maxn], n, m, a[maxn], b[maxn];
 30 struct TwoSat{
 31      int n;
 32      vector<int> G[maxn * 2];
 33      bool mark[maxn * 2];
 34      int S[maxn * 2], c;
 35      bool dfs(int x){ // 搜索一组解 
 36           if (mark[x^1]) return false; //出现冲突 
 37           if (mark[x]) return true;
 38           mark[x] = true;
 39           S[c++] = x;
 40           for (int i = 0; i < G[x].size(); ++i)
 41               if (!dfs(G[x][i])) return false;
 42           return true;
 43      }
 44 
 45      void init(int n){
 46           this->n = n;
 47           for (int i = 0; i < 2 * n; ++i)
 48               G[i].clear();
 49           memset(mark, 0, sizeof(mark));
 50      }
 51 
 52      void add_clause(int x, int xv, int y, int yv){
 53            x = x * 2 + xv;
 54            y = y * 2 + yv; //x,y不能同时存在，那么如果选了y，合法解必定要选x^1
 55            G[x^1].push_back(y);  
 56            G[y^1].push_back(x);
 57      }
 58 
 59      bool solve(){
 60            for (int i = 0; i < n * 2; i += 2)
 61                if (!mark[i] && !mark[i+1]){
 62                     c = 0;
 63                     if (!dfs(i)){ //枚举2种取值都无解 
 64                           while (c > 0) mark[S[--c]] = false;
 65                           if (!dfs(i+1)) return false;
 66                     }
 67                }
 68            return true;
 69      }
 70 } S;
 71 
 72 void init(){
 73      int x, y;
 74      for (int i = 0; i < n; ++i){
 75            scanf("%d%d", &x, &y);
 76            X[i] = x;
 77            Y[i] = y;
 78      }
 79      n *= 2; 
 80      for (int i = 1; i <= m; ++i)
 81           scanf("%d%d", &a[i], &b[i]);
 82 }
 83 
 84 bool check(int floor){
 85      S.init(n);
 86      for (int i = 0; i < n / 2; ++i){
 87            S.add_clause(X[i], 0, Y[i], 0); 
 88          //  S.add_clause(Y[i], 1, X[i], 1);
 89      }
 90      for (int i = 1; i <= floor; ++i){
 91            S.add_clause(a[i], 1, b[i], 1); 
 92           // S.add_clause(b[i], 0, a[i], 0);  
 93      }    
 94      return S.solve();
 95 }
 96 
 97 void solve(){
 98      int l = 1, r = m, ans = 0, mid;
 99      while (l <= r){
100           mid = (l + r) >> 1;
101           if (check(mid)){ans = mid; l = mid + 1; }
102           else r =  mid - 1;
103      }
104      printf("%d
", ans);
105 }
106 
107 int main(){
108    // freopen("a.in", "r", stdin);
109   //  freopen("a.out", "w", stdout);
110     while (scanf("%d%d", &n, &m) == 2 && n){
111          init();
112          solve();
113     }
114     fclose(stdin);  fclose(stdout);
115     return 0;
116 }

View Code

Poj2749

题意：

N 个牛栏，现在通过一条通道（s1,s2）把他们连起来，他们之间有一些约束关系，一些牛栏不能连在同一个点，一些牛栏必须连在同一个点，现在问有没有可能把他们都连好，而且满足所有的约束关系，如果可以，输出两个牛栏之间距离最大值的最小情况。

思路：

同样的二分答案。

至于建图：假定对于某个点a，连S1，为事件a，连S2，为事件~a

那么，对于不能连在一起的a, b两点，显然a与b，~a与~b互斥

另外一种情况则反过来。。

还有对于任意a与b，枚举他们的连接情况，一有矛盾同样建边。具体看代码吧

code：

  1 /*
  2  * Author:  Yzcstc
  3  * Created Time:  2014/3/12 14:56:50
  4  * File Name: Poj2749.cpp
  5  */
  6 #include<cstdio>
  7 #include<iostream>
  8 #include<cstring>
  9 #include<cstdlib>
 10 #include<cmath>
 11 #include<algorithm>
 12 #include<string>
 13 #include<map>
 14 #include<set>
 15 #include<vector>
 16 #include<queue>
 17 #include<stack>
 18 #include<ctime>
 19 #define M0(x) memset(x, 0, sizeof(x))
 20 #define rep(i, a, b) for (int i = (a); i <= (b); ++i)
 21 #define red(i, a, b) for (int i = (a); i >= (b); --i)
 22 #define PB push_back
 23 #define Inf 0x3fffffff
 24 #define eps 1e-8
 25 #define maxn 2000
 26 typedef long long LL;
 27 using namespace std;
 28 struct TwoSat{
 29        int n;
 30        bool mark[maxn];
 31        vector<int> G[maxn];
 32        int S[maxn], c;
 33        bool dfs(int x){
 34             if (mark[x^1]) return false;
 35             if (mark[x]) return true;
 36             mark[x] = true;
 37             S[c++] = x;
 38             for (int i = 0; i < G[x].size(); ++i)
 39                  if (!dfs(G[x][i])) return false;
 40             return true;
 41        }
 42 
 43        void init(int n){
 44             this->n = n;
 45             for (int i = 0; i < 2 * n; ++i) G[i].clear();
 46             memset(mark, 0, sizeof(mark));
 47        }
 48 
 49        void add_clause(int x, int xv, int y, int yv){
 50             x = x * 2 + xv;
 51             y = y * 2 + yv;
 52             G[x].push_back(y^1);
 53             G[y].push_back(x^1);
 54        }
 55 
 56        bool solve(){
 57             for (int i = 0; i < n * 2; i += 2)
 58                 if (!mark[i] && !mark[i+1]){
 59                       c = 0;
 60                       if (!dfs(i)){
 61                            while (c > 0) mark[S[--c]] = false;
 62                            if (!dfs(i+1)) return false;
 63                       }
 64                 }
 65             return true;
 66        }
 67 } S;
 68 int X[1200], Y[1200], F[1200][2], H[1200][2], n, A, B, d[1000][2], dst;
 69 int Sx1, Sx2, Sy1, Sy2;
 70 
 71 void init(){
 72      scanf("%d%d%d%d", &Sx1, &Sy1, &Sx2, &Sy2);
 73      for (int i = 0; i < n; ++i)
 74          scanf("%d%d", &X[i], &Y[i]);
 75      for (int i = 0; i < A; ++i)
 76          scanf("%d%d", &H[i][0], &H[i][1]), --H[i][0], --H[i][1];
 77      for (int i = 0; i < B; ++i)
 78          scanf("%d%d", &F[i][0], &F[i][1]), --F[i][0], --F[i][1];
 79 }
 80 
 81 int dist(int x1, int y1, int x2, int y2){
 82     return abs(x1 - x2) + abs(y1 - y2);
 83 }
 84 
 85 void get_dist(){
 86      dst = dist(Sx1, Sy1, Sx2, Sy2);
 87      for (int i = 0; i < n; ++i){
 88          d[i][0] = dist(X[i], Y[i], Sx1, Sy1);
 89          d[i][1] = dist(X[i], Y[i], Sx2, Sy2);
 90      }
 91 }
 92 
 93 bool check(int limit){
 94      S.init(n);
 95      for (int i = 0; i < A; ++i){
 96            S.add_clause(H[i][0], 0, H[i][1], 0);
 97            S.add_clause(H[i][0], 1, H[i][1], 1);
 98      }
 99      for (int i = 0; i < B; ++i){
100            S.add_clause(F[i][0], 0, F[i][1], 1);
101            S.add_clause(F[i][0], 1, F[i][1], 0);
102      }
103      int flag = 0;
104      for (int i = 0; i < n; ++i)
105          for (int j = i+1; j < n; ++j){
106               flag = 0;
107               if (d[i][0] + d[j][0] > limit) { S.add_clause(i, 0, j, 0); flag++; }
108               if (d[i][0] + d[j][1] + dst > limit) { S.add_clause(i, 0, j, 1); flag++; }
109               if (d[i][1] + d[j][0] + dst > limit) { S.add_clause(i, 1, j, 0); flag++; }
110               if (d[i][1] + d[j][1] > limit) { S.add_clause(i, 1, j, 1); flag++; }
111               if (flag == 4) return false;
112          }
113      return S.solve();
114 }
115 
116 void solve(){
117      get_dist();
118      int ans = -1;
119      int l = 0, r = 4000000, mid;
120      while (l <= r){
121           mid = (l + r) >> 1;
122           if (check(mid)){ans = mid; r = mid - 1; }
123           else l = mid + 1;
124      }
125      cout << ans << endl;
126 }
127 
128 int main(){
129   //  freopen("a.in", "r", stdin);
130    // freopen("a.out", "w", stdout);
131     while (scanf("%d%d%d", &n, &A, &B) == 3){
132           init();
133           solve();
134     }
135     fclose(stdin);  fclose(stdout);
136     return 0;
137 }

View Code

Poj3207：

题意：

一个圆上有n个点，依次从0到n-1，现在给出m条线段，每条连接两个点，线段可以在圆内也可以在圆外，问能否使得所有线段都不相交。

思路：

简单2-sat。对于两条相交的线段建边。。

code：

 1 /*
 2  * Author:  Yzcstc
 3  * Created Time:  2014/3/12 19:09:31
 4  * File Name: poj3207.cpp
 5  */
 6 #include<cstdio>
 7 #include<iostream>
 8 #include<cstring>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<algorithm>
12 #include<string>
13 #include<map>
14 #include<set>
15 #include<vector>
16 #include<queue>
17 #include<stack>
18 #include<ctime>
19 #define M0(x) memset(x, 0, sizeof(x))
20 #define rep(i, a, b) for (int i = (a); i <= (b); ++i)
21 #define red(i, a, b) for (int i = (a); i >= (b); --i)
22 #define PB push_back
23 #define Inf 0x3fffffff
24 #define eps 1e-8
25 #define maxn 2014
26 typedef long long LL;
27 using namespace std;
28 struct TwoSat{
29        int n;
30        int S[maxn], c;
31        bool mark[maxn];
32        vector<int> G[maxn];
33        bool dfs(int x){
34              if (mark[x^1]) return false;
35              if (mark[x]) return true;
36              mark[x] = true;
37              S[c++] = x;
38              for (int i = 0; i < G[x].size(); ++i)
39                  if (!dfs(G[x][i])) return false;
40              return true;
41        }
42 
43        void init(int n){
44              this->n = n;
45              for (int i = 0; i < n * 2; ++i) G[i].clear();
46              memset(mark, 0, sizeof(mark));
47        }
48 
49        void add_clause(int x, int y){
50             G[x].push_back(y^1);
51             G[y].push_back(x^1);
52        }
53        bool solve(){
54            for (int i = 0; i < n * 2; i += 2)
55            if (!mark[i] && !mark[i+1]){
56                   c = 0;
57                   if (!dfs(i)){
58                        while (c > 0) mark[S[--c]] = false;
59                        if (!dfs(i+1)) return false;
60                   }
61            }
62            return true;
63        }
64 } S;
65 int m, n, X[2014], Y[2014];
66 
67 bool In(int a, int b, int c){
68      if (a < b && a < c && c < b) return true;
69      if (a > b && (c > a || c < b)) return true;
70      return false;
71 }
72 void solve(){
73      for (int i = 0; i < n; ++i)
74         scanf("%d%d", &X[i], &Y[i]);
75      S.init(n);
76      for (int i = 0; i < n; ++i)
77         for (int j = i+1; j < n; ++j)
78              if (In(X[i], Y[i], X[j]) && In(Y[i], X[i], Y[j])
79                  || In(X[i], Y[i], Y[j]) && In(Y[i], X[i], X[j])){
80                      S.add_clause(i*2, j*2);
81                      S.add_clause(i*2+1, j*2+1);
82                  }
83      bool ans = S.solve();
84      if (ans) puts("panda is telling the truth...");
85      else puts("the evil panda is lying again");
86 }
87 
88 int main(){
89    // freopen("a.in", "r", stdin);
90   //  freopen("a.out", "w", stdout);
91     while (scanf("%d%d", &m, &n) == 2)  solve();
92     fclose(stdin);  fclose(stdout);
93     return 0;
94 }

View Code

Poj3648：

题意：

有一对新人结婚，邀请n对夫妇去参加婚礼。有一张很长的桌子，人只能坐在桌子的两边，还要满足下面的要求：1.每对夫妇不能坐在同一侧 2.n对夫妇之中可能有通奸关系（包括男男，男女，女女），有通奸关系的不能同时坐在新娘的对面，可以分开坐，可以同时坐在新娘这一侧。如果存在一种可行的方案，输出与新娘同侧的人。

思路：

算是这几道题比较容易错的了。

对于x与y通奸，则建x->~y, y->~x的边

而特殊的是新娘要与新郎连一条边，表示坐在对面

code：

  1 /*
  2  * Author:  Yzcstc
  3  * Created Time:  2014/3/12 20:08:13
  4  * File Name: poj3468.cpp
  5  */
  6 #include<cstdio>
  7 #include<iostream>
  8 #include<cstring>
  9 #include<cstdlib>
 10 #include<cmath>
 11 #include<algorithm>
 12 #include<string>
 13 #include<map>
 14 #include<set>
 15 #include<vector>
 16 #include<queue>
 17 #include<stack>
 18 #include<ctime>
 19 #define M0(x) memset(x, 0, sizeof(x))
 20 #define rep(i, a, b) for (int i = (a); i <= (b); ++i)
 21 #define red(i, a, b) for (int i = (a); i >= (b); --i)
 22 #define PB push_back
 23 #define Inf 0x3fffffff
 24 #define eps 1e-8
 25 #define maxn 50014
 26 typedef long long LL;
 27 using namespace std;
 28 struct TwoSat{
 29        int n;
 30        int S[maxn], c;
 31        bool mark[maxn];
 32        vector<int> G[maxn];
 33        bool dfs(int x){
 34              if (mark[x^1]) return false;
 35              if (mark[x]) return true;
 36              mark[x] = true;
 37              S[c++] = x;
 38              for (int i = 0; i < (int)G[x].size(); ++i)
 39                  if (!dfs(G[x][i])) return false;
 40              return true;
 41        }
 42 
 43        void init(int n){
 44              this->n = n;
 45              for (int i = 0; i < n * 2; ++i) G[i].clear();
 46              memset(mark, 0, sizeof(mark));
 47        }
 48 
 49        void add_clause(int x, int y){
 50             G[x^1].push_back(y);
 51             G[y^1].push_back(x);
 52        }
 53        bool solve(){
 54            for (int i = 0; i < n * 2; i += 2)
 55            if (!mark[i] && !mark[i+1]){
 56                   c = 0;
 57                   if (!dfs(i)){
 58                        while (c > 0) mark[S[--c]] = false;
 59                        if (!dfs(i+1)) return false;
 60                   }
 61            }
 62            return true;
 63        }
 64 } S;
 65 int n, m;
 66 
 67 void solve(){
 68      int x, y;
 69      char c1, c2;
 70      S.init(n);
 71      for (int i = 0; i < m; ++i){
 72           scanf("%d%c%d%c", &x, &c1, &y, &c2);
 73           x = x * 2;
 74           y = y * 2;
 75           if (c1 == 'h') ++x;
 76           if (c2 == 'h') ++y;
 77           S.add_clause(x, y);
 78      }
 79      S.G[1].push_back(0);
 80      if (!S.solve()){
 81             puts("bad luck");
 82             return;
 83      }
 84      for (int i = 1; i < n; ++i){
 85            if (S.mark[2*i]) printf("%dw", i);
 86            else printf("%dh", i);
 87            if (i == n-1) puts("");
 88            printf(" ");
 89      }
 90 }
 91 
 92 int main(){
 93    // freopen("a.in", "r", stdin);
 94   //  freopen("a.out", "w", stdout);
 95     while (scanf("%d%d", &n, &m) == 2 && n){
 96         // init();
 97          solve();
 98     }
 99     fclose(stdin);  fclose(stdout);
100     return 0;
101 }

View Code

poj3678：

题意：

有一个有向图G（V，E），每条边e（a,b）上有一个位运算符op（AND， OR或XOR）和一个值c（0或1）。

问能不能在这个图上的每个点分配一个值X（0或1），使得每一条边e(a,b)满足 Xa op Xb = c

思路：

a and b ==1 , !a->a , !b -> b

a and b ==0 , a->!b , b->!a

a or b ==1 , !a->b , !b->a

a or b ==0 , a->!a , b->!b

a xor b ==1 , a->!b,!b->a,!a->b,b->!a

a xor b ==0 , a->b,b->a,!a->!b,!b->!a

至于为什对于a && b == 1 要建立本身到本身反的边，是要推出矛盾。。

code：

  1 /*
  2  * Author:  Yzcstc
  3  * Created Time:  2014/3/16 21:06:08
  4  * File Name: poj3678.cpp
  5  */
  6 #include<cstdio>
  7 #include<iostream>
  8 #include<cstring>
  9 #include<cstdlib>
 10 #include<cmath>
 11 #include<algorithm>
 12 #include<string>
 13 #include<map>
 14 #include<set>
 15 #include<vector>
 16 #include<queue>
 17 #include<stack>
 18 #include<ctime>
 19 #define M0(x) memset(x, 0, sizeof(x))
 20 #define rep(i, a, b) for (int i = (a); i <= (b); ++i)
 21 #define red(i, a, b) for (int i = (a); i >= (b); --i)
 22 #define PB push_back
 23 #define Inf 0x3fffffff
 24 #define eps 1e-8
 25 #define maxn 4200
 26 typedef long long LL;
 27 using namespace std;
 28 struct TwoSat{
 29        int n;
 30        vector<int> G[maxn];
 31        bool mark[maxn];
 32        int c, S[maxn];
 33        bool dfs(int x){
 34              if (mark[x^1]) return false;
 35              if (mark[x]) return true;
 36              mark[x] = true;
 37              S[c++] = x;
 38              for (int i = 0; i < G[x].size(); ++i)
 39                    if (!dfs(G[x][i])) return false;
 40              return true;
 41        }
 42 
 43        void init(int n){
 44              this->n = n;
 45              memset(mark, 0, sizeof(mark));
 46              for (int i = 0; i < 2*n; ++i)
 47                   G[i].clear();
 48        }
 49 
 50        void add_clause(int x, int y){ G[x].push_back(y); }
 51 
 52        bool solve(){
 53              for (int i = 0; i < 2*n; 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 } S;
 65 int n, m;
 66 
 67 void solve(){
 68      char s[10];
 69      int a, b, c;
 70      S.init(n);
 71      for (int i = 0; i < m; ++i){
 72             scanf("%d%d%d%s", &a, &b, &c, &s);
 73             if (s[0] == 'A'){
 74                 if (c == 1) {  S.add_clause(a * 2, a * 2 + 1); S.add_clause(b * 2, b * 2 + 1); }
 75                 if (c == 0) {  S.add_clause(b * 2 + 1, a * 2); S.add_clause(a * 2 + 1, b * 2); }
 76             }
 77             if (s[0] == 'O'){
 78                 if (c == 1) {  S.add_clause(b * 2, a * 2 + 1); S.add_clause(a * 2, b * 2 + 1); }
 79                 if (c == 0) {  S.add_clause(a * 2 + 1, a * 2); S.add_clause(b * 2 + 1, b * 2); }
 80             }
 81             if (s[0] == 'X'){
 82                  if (c == 1) {  S.add_clause(b * 2, a * 2 + 1); S.add_clause(a * 2, b * 2 + 1);
 83                                 S.add_clause(b * 2 + 1, a * 2); S.add_clause(a * 2 + 1, b * 2);
 84                              }
 85                  if (c == 0) {  S.add_clause(b * 2, a * 2); S.add_clause(a * 2, b * 2);
 86                                 S.add_clause(b * 2 + 1, a * 2 + 1); S.add_clause(a * 2 + 1, b * 2 + 1);
 87                              }
 88             }
 89      }
 90      if (S.solve()) puts("YES");
 91      else puts("NO");
 92 }
 93 
 94 int main(){
 95    // freopen("a.in", "r", stdin);
 96    // freopen("a.out", "w", stdout);
 97     while (scanf("%d%d", &n, &m) == 2) solve();
 98     fclose(stdin);  fclose(stdout);
 99     return 0;
100 }

View Code

Poj3683：

题意：

　有一个牧师要给好几对新婚夫妇准备婚礼.，已知每对新婚夫妇的有空的时间以及婚礼持续时间..

　问是否可以让每对新婚夫妇都得到该牧师的祝福。如果可以就输出YES以及可行解不可以就输出NO

思路：

典型的2-sat。只不过多了输出解。

code：

  1 /*
  2  * Author:  Yzcstc
  3  * Created Time:  2014/3/18 18:06:09
  4  * File Name: poj3683.cpp
  5  */
  6 #include<cstdio>
  7 #include<iostream>
  8 #include<cstring>
  9 #include<cstdlib>
 10 #include<cmath>
 11 #include<algorithm>
 12 #include<string>
 13 #include<map>
 14 #include<set>
 15 #include<vector>
 16 #include<queue>
 17 #include<stack>
 18 #include<ctime>
 19 #define M0(x) memset(x, 0, sizeof(x))
 20 #define rep(i, a, b) for (int i = (a); i <= (b); ++i)
 21 #define red(i, a, b) for (int i = (a); i >= (b); --i)
 22 #define PB push_back
 23 #define Inf 0x3fffffff
 24 #define maxn 8000
 25 #define eps 1e-8
 26 typedef long long LL;
 27 using namespace std;
 28 struct TwoSat{
 29        int n;
 30        vector<int> G[maxn];
 31        int c, S[maxn];
 32        bool mark[maxn];
 33        bool dfs(int x){
 34              if (mark[x^1]) return false;
 35              if (mark[x]) return true;
 36              mark[x] = true;
 37              S[c++] = x;
 38              for (int i = 0; i < G[x].size(); ++i)
 39                   if (!dfs(G[x][i])) return false;
 40              return true;
 41        }
 42 
 43        void init(int n){
 44              this->n = n;
 45              memset(mark, 0, sizeof(mark));
 46              for (int i = 0; i < 2*n; ++i)
 47                   G[i].clear();
 48        }
 49        void add_clause(int x, int y){
 50              G[x^1].push_back(y);
 51              G[y^1].push_back(x);
 52        }
 53        bool solve(){
 54              for (int i = 0; i < 2*n; i += 2)
 55                 if (!mark[i] && !mark[i+1]){
 56                        c = 0;
 57                        if (!dfs(i)){
 58                              while (c > 0) mark[S[--c]] = false;
 59                              if (!dfs(i+1)) return false;
 60                        }
 61                 }
 62              return true;
 63        }
 64 } S;
 65 int n;
 66 int St[2048], En[2048], D[2048];
 67 bool g[2048][2048];
 68 
 69 void init(){
 70      int x, y, x2, y2, z;
 71      for (int i = 0; i < n; ++i){
 72          scanf("%d:%d %d:%d %d", &x, &y, &x2, &y2, &z);
 73          D[i] = z;
 74          St[i] = x * 60 + y;
 75          En[i] = x2 * 60 + y2;
 76      }
 77 }
 78 
 79 bool check(int S1, int T1, int S2, int T2){
 80      if (S1 < T2 && S2 < T1) return true;
 81      return false;
 82 }
 83 
 84 void solve(){
 85      S.init(n);
 86      int S1, T1, S2, T2;
 87      M0(g);
 88      for (int i = 0; i < n; ++i)
 89        for (int j = i + 1; j < n; ++j){
 90              S1 = St[i],  T1 = St[i] + D[i];
 91              S2 = St[j],  T2 = St[j] + D[j];
 92              if (check(S1, T1, S2, T2)){ g[i*2][j * 2] = true; S.add_clause(i * 2, j * 2); }
 93              S1 = St[i],  T1 = St[i] + D[i];
 94              S2 = En[j] - D[j],  T2 = En[j];
 95              if (check(S1, T1, S2, T2)) { g[i*2][j*2+1] = true; S.add_clause(i * 2, j * 2 + 1);}
 96              S1 = En[i] - D[i],  T1 = En[i];
 97              S2 = St[j],  T2 = St[j] + D[j];
 98              if (check(S1, T1, S2, T2)) { g[i*2+1][j*2] = true; S.add_clause(i * 2 + 1, j * 2);}
 99              S1 = En[i] - D[i],  T1 = En[i];
100              S2 = En[j] - D[j],  T2 = En[j];
101              if (check(S1, T1, S2, T2)) { g[i*2+1][j*2+1] = true; S.add_clause(i * 2 + 1, j * 2 + 1);}
102        }
103      if (!S.solve()){puts("NO"); return;}
104      puts("YES");
105      vector<int> V;
106      for (int i = 0; i < n; ++i)
107         if (S.mark[i*2]) V.PB(i*2);
108         else V.PB(i*2+1);
109      bool flag = true;
110      for (int i = 0; i < V.size(); ++i)
111          for (int j = i+1; j < V.size(); ++j)
112             if (g[V[i]][V[j]] || g[V[j]][V[i]]) flag = false;
113      for (int i = 0; i < n; ++i){
114          if (S.mark[i*2] == flag){
115                printf("%02d:%02d %02d:%02d
", St[i] / 60, St[i] % 60, (St[i] + D[i]) / 60, (St[i] + D[i]) % 60);
116                continue;
117          }
118          printf("%02d:%02d %02d:%02d
", (En[i] - D[i]) / 60, (En[i] - D[i]) % 60, En[i] / 60, En[i] % 60);
119      }
120 }
121 
122 int main(){
123    // freopen("a.in", "r", stdin);
124   //  freopen("a.out", "w", stdout);
125     while (scanf("%d", &n) != EOF){
126          init();
127          solve();
128     }
129     fclose(stdin);  fclose(stdout);
130     return 0;
131 }

View Code

Poj3905

题意：

有n个候选人，m组要求，每组要求关系到候选人中的两个人，“+i +j”代表i和j中至少有一人被选中，“-i -j”代表i和j中至少有一人不被选中。“+i -j”代表i被选中和j不被选中这两个事件至少发生一个，“-i +j”代表i不被选中和j被选中这两个事件至少发生一个。问是否存在符合所有m项要求的方案存在。

思路：

简单的2-sat

code：

 1 /*
 2  * Author:  Yzcstc
 3  * Created Time:  2014/3/19 0:06:34
 4  * File Name: poj3905.cpp
 5  */
 6 #include<cstdio>
 7 #include<iostream>
 8 #include<cstring>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<algorithm>
12 #include<string>
13 #include<map>
14 #include<set>
15 #include<vector>
16 #include<queue>
17 #include<stack>
18 #include<ctime>
19 #define M0(x) memset(x, 0, sizeof(x))
20 #define rep(i, a, b) for (int i = (a); i <= (b); ++i)
21 #define red(i, a, b) for (int i = (a); i >= (b); --i)
22 #define PB push_back
23 #define Inf 0x3fffffff
24 #define eps 1e-8
25 #define maxn 4000
26 typedef long long LL;
27 using namespace std;
28 struct Twosat{
29        int n;
30        int S[maxn], c;
31        vector<int> G[maxn];
32        bool mark[maxn];
33        bool dfs(int x){
34             if (mark[x^1]) return false;
35             if (mark[x]) return  true;
36             mark[x] = true;
37             S[c++] = x;
38             for (int i = 0; i < G[x].size(); ++i)
39                 if (!dfs(G[x][i])) return false;
40             return true;
41        }
42        void init(int n){
43             this->n = n;
44             memset(mark, 0, sizeof(mark));
45             for (int i = 0; i < 2 * n; ++i)
46                  G[i].clear();
47        }
48        void add_clause(int x, int y){
49             G[x^1].PB(y);
50             G[y^1].PB(x);
51        }
52        bool solve(){
53              for (int i = 0; i < 2*n; 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 } S;
64 int n, m;
65 
66 int change(char s[], int n){
67      int ret = 0;
68      for (int i = 0; i < n; ++i)
69          if(s[i] <= '9' && s[i] >= '0') ret = ret * 10 + s[i] - 48;
70      return ret;
71 }
72 
73 void solve(){
74      int x, y;
75      char s[20], s1[20];
76      S.init(n);
77      for (int i = 0; i < m; ++i){
78            scanf("%s%s", &s, &s1);
79            x = change(s, strlen(s)) - 1;
80            y = change(s1, strlen(s1)) - 1;
81            if (s[0] == '+' && s1[0] == '+') S.add_clause(x * 2 + 1, y * 2 + 1);
82            if (s[0] == '+' && s1[0] == '-') S.add_clause(x * 2 + 1, y * 2);
83            if (s[0] == '-' && s1[0] == '+') S.add_clause(x * 2, y * 2 + 1);
84            if (s[0] == '-' && s1[0] == '-') S.add_clause(x * 2, y * 2);
85      }
86      if (S.solve()) puts("1");
87      else puts("0");
88 }
89 
90 int main(){
91   //  freopen("a.in", "r", stdin);
92   //  freopen("a.out", "w", stdout);
93     while (scanf("%d%d", &n, &m) == 2) solve();
94     fclose(stdin);  fclose(stdout);
95     return 0;
96 }

View Code