UVAlive3211 Now or later（2-SAT）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33799

【思路】

2-SAT。

二分安全间隔x，先到为1后到为0，则唯一的限制即两个不同的时间a b如果其间隔小于x则不能满足(a=1 and b=1)，即满足 (a or b)=1，如果满足所有的约束条件则x可行。

时间复杂度为O(logt*n^2)。

【代码】

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int maxn = +;

 struct TwoSAT {

     int n;

     vector<int> G[maxn*];

     bool mark[maxn*];

     int S[maxn*],c;

     void init(int n) {

         this->n=n;

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

         memset(mark,,sizeof(mark));

     }

     void addc(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 dfs(int x) {

         if(mark[x^]) return false;

         if(mark[x]) return true;

         mark[x]=true;

         S[c++]=x;

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

             if(!dfs(G[x][i])) return false;

         return true;

     }

     bool solve() {

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

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

                 c=;

                 if(!dfs(i)) {

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

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

                 }

             }

         return true;

     }

 }ts;

 int n;

 int t[maxn][];

 bool can(int M) {

     ts.init(n);

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

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

             if(abs(t[i][a]-t[j][b])<M) ts.addc(i,a^,j,b^);

     return ts.solve();

 }

 int main() {

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

         int L=,R=;

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

             scanf("%d%d",&t[i][],&t[i][]);

             R=max(R,t[i][]);

         }

         while(L<R) {

             int M=L+(R-L+)/;

             if(can(M)) L=M; else R=M-;

         }

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

     }

     return ;

 }