poj2723-Get Luffy Out

一道2-SAT问题，每对钥匙需要加一条边，每扇门上的对应的要用的钥匙加一条边。

其实求解2-SAT问题，关键在于找到不能同时成立的条件，例如在本题中，每对钥匙不能同时使用，每扇门上的钥匙不能同时不使用。

 #include<cstdio>

 #include<vector>

 #include<cstring>

 using namespace std;

 const int maxn = <<;

 struct TwoSAT

 {

     int n;

     vector<int> G[maxn*];

     bool mark[maxn*];

     int S[maxn*], c;

     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;

     }

     void init(int n)

     {

         this->n = n;

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

         memset(mark, , sizeof(mark));

     }

     // x = xval or y = yval

     void add_clause(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]] = false;

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

                 }

             }

         return true;

     }

 };

 ///////////////////////////////////////////////////////////////

 #include <iostream>

 TwoSAT solver;

 typedef pair<int ,int > CPair;

 #define K1 first

 #define K2 second

 CPair doors[<<];

 CPair keys[<<];

 int n;

 bool test(int nd)

 {

     solver.init(*n);

     // 重新构图

     // 加入钥匙

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

     {

         solver.add_clause(keys[i].K1,,keys[i].K2,); // 1表示使用key，0表示不使用

     }

     // 加入门

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

     {

         solver.add_clause(doors[i].K1,,doors[i].K2,); // 1表示使用key，0表示不使用

     }

     return solver.solve();

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

     freopen("in.txt","r",stdin);

     #endif

     int nDoor;

     while(scanf("%d %d",&n,&nDoor),n+nDoor)

     {

         // 添加一对钥匙

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

         {

             scanf("%d %d",&keys[i].K1,&keys[i].K2);

         }

         // 门

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

         {

             scanf("%d %d",&doors[i].K1,&doors[i].K2);

         }

         int L=,R=nDoor-;

         while(L < R)

         {

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

             if(test(M)) L = M;

             else R = M-;

         }

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

     }

     return ;

 }