題意：
? ? ?有m層門，我們在最外層，我們要一層一層的進，每一層上有兩把鎖，我們只要開啟其中的一把們就會開，我們有n組鑰匙，每組兩把，我們只能用其中的一把，用完后第二把瞬間就會消失，問你最多能開到多少層們。

思路：

? ? ? 果斷二分+2sat，現在我們來看下怎么建邊，首先我們把每把鑰匙用看成a,不用看成~a ,對于沒一組鑰匙，我們不能同時選擇兩個，所以有 x ->~y ,y -> ~x,對于門，我們每次至少選擇開一個，所以有 ~x -> y ,~y -> x,就這樣二分每次重新建圖就行了，順便說下POJ2723 ，跟這個題目幾乎差不多，但是唯一的區別就是那個題目每組鑰匙不會重復，這個有可能是同一把鑰匙屬于多個組，如果用這個題目的代碼直接去交POJ2723，直接就可以AC了，鑰匙反過來就不一定了，因為那個題目既然說是一把鑰匙最多只出現在一組，那么就沒有必要把每把鑰匙拆成a 和 ~a ，而是把每組的鑰匙拆成 a ~a,這樣就節省了點數和時間，同時也沒有必要建 x ->~y y->~x,這樣也節省的邊，如果是那么做的，那么到這個題目上就WA了，所以我說這個代碼粘到那個代碼上肯定AC，反過來就不一定了。

#include<stdio.h> #include<string.h> #include<stack>#define N_node 5000 #define N_edge 50000 using namespace std;typedef struct {int to ,next; }STAR;STAR E1[N_edge] ,E2[N_edge]; int list1[N_node] ,list2[N_node] ,tot; int Belong[N_node] ,cnt; int mark[N_node]; int D[N_node][2] ,A[N_node][2]; int id[N_node]; stack<int>st;void add(int a ,int b) {E1[++tot].to = b;E1[tot].next = list1[a];list1[a] = tot;a = a + b ,b = a - b ,a = a - b;E2[tot].to = b;E2[tot].next = list2[a];list2[a] = tot; }void DFS1(int s) {mark[s] = 1;for(int k = list1[s] ;k ;k = E1[k].next)if(!mark[E1[k].to]) DFS1(E1[k].to);st.push(s); }void DFS2(int s) {mark[s] = 1;Belong[s] = cnt;for(int k = list2[s] ;k ;k = E2[k].next)if(!mark[E2[k].to]) DFS2(E2[k].to); }bool ok(int mid ,int n) {memset(list1 ,0 ,sizeof(list1));memset(list2 ,0 ,sizeof(list2));tot = 1;for(int i = 1 ; i<= n/2 ;i ++){int x = A[i][0] * 2 ,xx = A[i][0] * 2 + 1;int y = A[i][1] * 2 ,yy = A[i][1] * 2 + 1;add(x ,yy) ,add(y ,xx);}for(int i = 1 ;i <= mid ;i ++){ int x = D[i][0] * 2 ,xx = D[i][0] * 2 + 1;int y = D[i][1] * 2 ,yy = D[i][1] * 2 + 1;add(xx ,y) ,add(yy ,x);}memset(mark ,0 ,sizeof(mark));while(!st.empty()) st.pop();for(int i = 0 ;i < n * 2 ;i ++)if(!mark[i]) DFS1(i);memset(mark ,0 ,sizeof(mark));cnt = 0;while(!st.empty()){int xin = st.top();st.pop();if(mark[xin]) continue;cnt ++;DFS2(xin);}int mk = 0;for(int i = 0 ;i < n * 2 && !mk;i += 2)if(Belong[i] == Belong[i^1]) mk = 1;return !mk; }int main () {int i ,n ,m ,a ,b;while(~scanf("%d %d" ,&n ,&m) && n + m){for(i = 1 ;i <= n ;i ++){scanf("%d %d" ,&a ,&b);A[i][0] = a ,A[i][1] = b;}for(i = 1 ;i <= m ;i ++)scanf("%d %d" ,&D[i][0] ,&D[i][1]); int low ,up , mid ,ans = 0;low = 0 ,up = m ,n *= 2;while(low <= up){mid = (low + up) >> 1;if(ok(mid ,n))ans = mid ,low = mid + 1;else up = mid - 1;}printf("%d\n" ,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu1816 + POJ 2723开锁（二分+2sat）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。