2-SAT两题

　　看了大白书，学习了一下two-sat，很有意思的算法。题目就是大白书上的两题。

　　仅仅放一下代码作为以后的模板参考。

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <vector>
 5 using namespace std;
 6 const int N = 2000 + 50;
 7 
 8 struct TwoSAT
 9 {
10     int n;
11     vector<int> G[N*2];
12     bool mark[N*2];
13     int S[N*2], c;
14 
15     bool dfs(int x)
16     {
17         if(mark[x^1]) return 0;
18         if(mark[x]) return 1;
19         mark[x] = 1;
20         S[c++] = x;
21         for(int i=0;i<G[x].size();i++)
22         {
23             int v = G[x][i];
24             if(!dfs(v)) return false;
25         }
26         return true;
27     }
28     
29     void init(int n)
30     {
31         this->n = n;
32         for(int i=0;i<2*n;i++) G[i].clear();
33         memset(mark,false,sizeof(mark));
34     }
35     
36     void addEdge(int x,int xval,int y,int yval)
37     {
38         x = x * 2 + xval;
39         y = y * 2 + yval;
40         G[x^1].push_back(y);
41         G[y^1].push_back(x);
42     }
43     
44     bool solve()
45     {
46         for(int i=0;i<2*n;i+=2)
47         {
48             if(!mark[i] && !mark[i+1])
49             {
50                 c = 0;
51                 if(!dfs(i))
52                 {
53                     while(c > 0) mark[S[--c]] = 0;
54                     if(!dfs(i + 1)) return false;
55                 }
56             }
57         }
58         return true;
59     }
60 }solver;
61 
62 int n;
63 int T[N][2];
64 bool can(int dif)
65 {
66     solver.init(n);
67     for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
68         for(int a=0;a<2;a++) for(int b=0;b<2;b++)
69         {
70             if(std::abs(T[i][a] - T[j][b]) < dif) solver.addEdge(i,a^1,j,b^1);
71         }
72     return solver.solve();
73 }
74 
75 int main()
76 {
77     while(scanf("%d",&n) == 1)
78     {
79         int L = 0, R = 0;
80         for(int i=0;i<n;i++) for(int j=0;j<2;j++) {scanf("%d",&T[i][j]); R = max(R, T[i][j]);}
81         int ans = -1;
82         while(L <= R)
83         {
84             int mid = L + R >> 1;
85             if(can(mid)) {ans = mid; L = mid + 1;}
86             else R = mid - 1;
87         }
88         printf("%d
",ans);
89     }
90     return 0;
91 }

UVALive - 3211

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <vector>
  5 using namespace std;
  6 const int N = 1e5 + 50;
  7 
  8 struct TwoSAT
  9 {
 10     int n;
 11     vector<int> G[N*2];
 12     bool mark[N*2];
 13     int S[N*2], c;
 14 
 15     bool dfs(int x)
 16     {
 17         if(mark[x^1]) return 0;
 18         if(mark[x]) return 1;
 19         mark[x] = 1;
 20         S[c++] = x;
 21         for(int i=0;i<G[x].size();i++)
 22         {
 23             int v = G[x][i];
 24             if(!dfs(v)) return false;
 25         }
 26         return true;
 27     }
 28     
 29     void init(int n)
 30     {
 31         this->n = n;
 32         for(int i=0;i<2*n;i++) G[i].clear();
 33         memset(mark,false,sizeof(mark));
 34     }
 35     
 36     void addEdge(int x,int xval,int y,int yval)
 37     {
 38         x = x * 2 + xval;
 39         y = y * 2 + yval;
 40         G[x^1].push_back(y);
 41         G[y^1].push_back(x);
 42     }
 43     
 44     bool solve()
 45     {
 46         for(int i=0;i<2*n;i+=2)
 47         {
 48             if(!mark[i] && !mark[i+1])
 49             {
 50                 c = 0;
 51                 if(!dfs(i))
 52                 {
 53                     while(c > 0) mark[S[--c]] = 0;
 54                     if(!dfs(i + 1)) return false;
 55                 }
 56             }
 57         }
 58         return true;
 59     }
 60 }solver;
 61 
 62 int n,m;
 63 int p[N];
 64 char get(bool mark,bool flag)
 65 {
 66     if(flag) return mark ? 'A' : 'C';
 67     else return mark ? 'B' : 'C';
 68 }
 69 
 70 int main()
 71 {
 72     while(scanf("%d%d",&n,&m) == 2)
 73     {
 74         if(n == 0 && m == 0) break;
 75         solver.init(n);
 76         int sum = 0;
 77         for(int i=0;i<n;i++) scanf("%d",p+i), sum += p[i];
 78 
 79         for(int i=0;i<m;i++)
 80         {
 81             int a,b;
 82             scanf("%d%d",&a,&b);
 83             a--, b--;
 84             if(n * p[a] >= sum && n * p[b] >= sum || n * p[a] < sum && n * p[b] < sum)
 85             {
 86                 solver.addEdge(a,1,b,1);
 87                 solver.addEdge(a,0,b,0);
 88             }
 89             else solver.addEdge(a,1,b,1);
 90         }
 91         if(solver.solve() == false) puts("No solution.");
 92         else
 93         {
 94             for(int i=0;i<2*n;i+=2)
 95             {
 96                 if(solver.mark[i]) puts("C");
 97                 else if(n * p[i / 2] >= sum) puts("A");
 98                 else puts("B");
 99             }
100         }
101     }
102     return 0;
103 }

UVALive - 3713