2-SAT两题

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

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

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 using namespace std;

 const int N =  + ;

 struct TwoSAT

 {

     int n;

     vector<int> G[N*];

     bool mark[N*];

     int S[N*], c;

     bool dfs(int x)

     {

         if(mark[x^]) return ;

         if(mark[x]) return ;

         mark[x] = ;

         S[c++] = x;

         for(int i=;i<G[x].size();i++)

         {

             int v = G[x][i];

             if(!dfs(v)) return false;

         }

         return true;

     }

     void init(int n)

     {

         this->n = n;

         for(int i=;i<*n;i++) G[i].clear();

         memset(mark,false,sizeof(mark));

     }

     void addEdge(int x,int xval,int y,int yval)

     {

         x = x *  + xval;

         y = y *  + yval;

         G[x^].push_back(y);

         G[y^].push_back(x);

     }

     bool solve()

     {

         for(int i=;i<*n;i+=)

         {

             if(!mark[i] && !mark[i+])

             {

                 c = ;

                 if(!dfs(i))

                 {

                     while(c > ) mark[S[--c]] = ;

                     if(!dfs(i + )) return false;

                 }

             }

         }

         return true;

     }

 }solver;

 int n;

 int T[N][];

 bool can(int dif)

 {

     solver.init(n);

     for(int i=;i<n;i++) for(int j=i+;j<n;j++)

         for(int a=;a<;a++) for(int b=;b<;b++)

         {

             if(std::abs(T[i][a] - T[j][b]) < dif) solver.addEdge(i,a^,j,b^);

         }

     return solver.solve();

 }

 int main()

 {

     while(scanf("%d",&n) == )

     {

         int L = , R = ;

         for(int i=;i<n;i++) for(int j=;j<;j++) {scanf("%d",&T[i][j]); R = max(R, T[i][j]);}

         int ans = -;

         while(L <= R)

         {

             int mid = L + R >> ;

             if(can(mid)) {ans = mid; L = mid + ;}

             else R = mid - ;

         }

         printf("%d\n",ans);

     }

     return ;

 }

UVALive - 3211

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 using namespace std;

 const int N = 1e5 + ;

 struct TwoSAT

 {

     int n;

     vector<int> G[N*];

     bool mark[N*];

     int S[N*], c;

     bool dfs(int x)

     {

         if(mark[x^]) return ;

         if(mark[x]) return ;

         mark[x] = ;

         S[c++] = x;

         for(int i=;i<G[x].size();i++)

         {

             int v = G[x][i];

             if(!dfs(v)) return false;

         }

         return true;

     }

     void init(int n)

     {

         this->n = n;

         for(int i=;i<*n;i++) G[i].clear();

         memset(mark,false,sizeof(mark));

     }

     void addEdge(int x,int xval,int y,int yval)

     {

         x = x *  + xval;

         y = y *  + yval;

         G[x^].push_back(y);

         G[y^].push_back(x);

     }

     bool solve()

     {

         for(int i=;i<*n;i+=)

         {

             if(!mark[i] && !mark[i+])

             {

                 c = ;

                 if(!dfs(i))

                 {

                     while(c > ) mark[S[--c]] = ;

                     if(!dfs(i + )) return false;

                 }

             }

         }

         return true;

     }

 }solver;

 int n,m;

 int p[N];

 char get(bool mark,bool flag)

 {

     if(flag) return mark ? 'A' : 'C';

     else return mark ? 'B' : 'C';

 }

 int main()

 {

     while(scanf("%d%d",&n,&m) == )

     {

         if(n ==  && m == ) break;

         solver.init(n);

         int sum = ;

         for(int i=;i<n;i++) scanf("%d",p+i), sum += p[i];

         for(int i=;i<m;i++)

         {

             int a,b;

             scanf("%d%d",&a,&b);

             a--, b--;

             if(n * p[a] >= sum && n * p[b] >= sum || n * p[a] < sum && n * p[b] < sum)

             {

                 solver.addEdge(a,,b,);

                 solver.addEdge(a,,b,);

             }

             else solver.addEdge(a,,b,);

         }

         if(solver.solve() == false) puts("No solution.");

         else

         {

             for(int i=;i<*n;i+=)

             {

                 if(solver.mark[i]) puts("C");

                 else if(n * p[i / ] >= sum) puts("A");

                 else puts("B");

             }

         }

     }

     return ;

 }

UVALive - 3713