UVALive 3211 Now or later（2-sat）

2-sat问题，一种在两种可能性中选择必然关系的问题。

推荐两篇论文，也是学2-sat公认比较好的材料。前者较好理解，后者需耐心看。

http://www.google.com.hk/url?sa=t&rct=j&q=2-sat&source=web&cd=6&ved=0CEUQFjAF&url=http%3a%2f%2fbbs%2ebyr%2ecn%2fwForum%2fboardcon%2ephp%3fbid%3d212%26id%3d15887%26ftype%3d3%26ap%3d369&ei=30wAUsrlDYLHkwXam4GoBA&usg=AFQjCNHn7CqQ5EIiXNyfUmYM7jYYsIMfeQ&bvm=bv.50165853,d.dGI&cad=rjt

http://bbs.byr.cn/wForum/boardcon.php?bid=212&id=15890&ftype=3&ap=278

“最小值尽量大”问题，又是一种经典模型，二分答案，从而判断是否能构建出合适的方案。

代码看书码的，注意几点：

不能缩点，会把不成立的情况缩掉，所以改为标记。

一旦任意一点的两种可能性都不成立，即不存在完整的方案。

本题只是二选一，A或B的一种形式来建边的，其他形式的2-sat要通过做题去接触，不过，总的来说都是根据必然关系建图。

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

View Code