LA3211二分答案+2-sat+总结的此类问题统一建模方法

  1 /*LA3211
  2 2-sat+二分答案
  3 现在统一建模的方式：
  4 1、同一组的两个状态分别存储在2*i和2*i+1两个节点，产生2*n个节点
  5 2、for(int i=1;i<2*n;i++)
  6    for(int j=0;j<i;j++)
  7    {
  8       if (i==(j^1)) continue;
  9       sat.add_clause(i,j);//枚举出的不属于同一组的不相容的两点
 10    }
 11 3、2-sat即可
 12 和HDU3622相似
 13 */
 14 #include <stdio.h>
 15 #include <stdlib.h>
 16 #include <string.h>
 17 #include <math.h>
 18 #include <ctype.h>
 19 #include <string>
 20 #include <iostream>
 21 #include <sstream>
 22 #include <vector>
 23 #include <queue>
 24 #include <stack>
 25 #include <map>
 26 #include <list>
 27 #include <set>
 28 #include <algorithm>
 29 #define INF 0x3f3f3f3f
 30 #define LL long long
 31 #define eps 1e-4
 32 #define maxn 2010
 33 using namespace std;
 34 int T[2*maxn];
 35 struct TwoSAT
 36 {
 37     int n;
 38     vector<int> G[maxn*2];
 39     bool mark[maxn*2];//联系《2-sat算法解析》中的红蓝标色
 40     int S[maxn*2],c;
 41     bool dfs(int x)
 42     {
 43         if (mark[x^1]) return false;//真假同时被标记，逻辑矛盾
 44         if (mark[x]) return true;//x被标记，意味着下面的节点也被标记，思想是记忆化搜索
 45         mark[x]=true;
 46         S[c++]=x;
 47         for(int i=0; i<G[x].size(); i++)
 48         if(!dfs(G[x][i])) return false; //同一个强联通分量应该表上同一种颜色
 49         return true;
 50     }
 51     void init(int n)
 52     {
 53         this->n=n;
 54         for(int i=0; i<n*2; i++) G[i].clear();
 55         memset(mark,0,sizeof(mark));
 56     }
 57     //x=xval or y=xval ，x 则 xval=0，x‘则xval=1
 58     void add_clause(int x ,int y)
 59     {
 60         G[x].push_back(y^1);
 61         G[y].push_back(x^1);
 62     }
 63     bool solve()
 64     {
 65         for(int i=0;i<n*2;i+=2)
 66         {
 67             if(!mark[i] && !mark[i^1])//真假都没被标记才需dfs，思考一下，原书上写的是[mark+1],这是由i的取值和步长决定的，这里更改，使逻辑含义统一
 68             {
 69                 c=0;//记得清零
 70                 if(!dfs(i))//将i标记为true
 71                 {
 72                     while(c>0) mark[S[--c]]=false;
 73                     if (!dfs(i^1)) return false;//更改初始标号颜色。只要有一个对象不能“二选一”，则2-sat无解
 74                 }
 75             }
 76         }
 77         return true;
 78     }
 79 } sat;
 80 double dis(double x1,double y1,double x2,double y2)
 81 {
 82     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 83 }
 84 int n;
 85 bool solve(int time)
 86 {
 87     sat.init(n);
 88     for(int i=1;i<2*n;i++)//枚举
 89     {
 90         for(int j=0;j<i;j++)
 91         {
 92             if (i==(j^1)) continue;//消除所有的同一组的
 93             if (time>abs(T[i]-T[j])) sat.add_clause(i,j);
 94         }
 95     }
 96     return sat.solve();
 97 }
 98 int nextint(){int x;scanf("%d",&x);return x;}
 99 int main()
100 {
101     while(cin>>n)
102     {
103         for(int i=0;i<n;i++)
104         {
105             T[i*2]=nextint();
106             T[i*2+1]=nextint();
107         }
108         int L=0,R=10000001;
109         while(R>L)
110         {
111             int M=(L+R+1)/2;
112             if (!solve(M)) R=M-1;else L=M;
113         }
114         cout<<L<<endl;
115         //貌似printf不能配合ceil使用 = =~
116         //最终结果要求是整数，要满足实际意义
117     }
118     return 0;
119 }