1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 using namespace std; 5  6 const int maxn = _____; 7  8 struct TwoSAT 9 {10     int n;11     vector<int> G[maxn*2];12     bool mark[maxn*2];13     int S[maxn*2], c;14 15     bool dfs(int x)16     {17         if (mark[x^1]) return false;18         if (mark[x]) return true;19         mark[x] = true;20         S[c++] = x;21         for (int i = 0; i < G[x].size(); i++)22             if (!dfs(G[x][i])) return false;23         return true;24     }25 26     void init(int n) // 一定要注意初始化的点数，别弄错27     {28         this->n = n;29         for (int i = 0; i < n*2; i++) G[i].clear();30         memset(mark, 0, sizeof(mark));31     }32 33     // x = xval or y = yval34     void add_clause(int x, int xval, int y, int yval) // 编号从0~n-135     {36         x = x * 2 + xval;37         y = y * 2 + yval;38         G[x^1].push_back(y);39         G[y^1].push_back(x);40     }41 42     bool solve()43     {44         for(int i = 0; i < n*2; i += 2)45             if(!mark[i] && !mark[i+1])46             {47                 c = 0;48                 if(!dfs(i))49                 {50                     while(c > 0) mark[S[--c]] = false;51                     if(!dfs(i+1)) return false;52                 }53             }54         return true;55     }56 };57 58 TwoSAT solver;59 ////////////////////////////////////////////////////60 //二分搜索，2-SAT中经常会用到61         int L=____,R=____;62         while(L < R)63         {64             int M = L + (R-L+1)/2;65             if(test(M)) L = M; // M满足条件的话test返回真66             else R = M-1;67         }68         printf("%d\n",L);