算法：POJ 2723 Get Luffy Out（2-SAT + 二分）

算法：POJ 2723 Get Luffy Out（2-SAT + 二分）2014-01-10 csdn shuangde800【题目大意】

有2*N把不同的锁，每把锁有一个钥匙，所以共有2*N 把钥匙。把2*N把钥匙两两配对共分为N组。

有个M层楼，每层楼有一个门，每个门上有两把锁，可能是相同的也可能是不同的。走上某层楼之前，必须要打开这个门上的至少一个锁。

要你从每组钥匙中选择一把钥匙，然后用这些钥匙去上这栋楼，问最多能走到几层楼？

【思路】

对于每组钥匙，只能二取一，所以是2 -SAT模型。

问题是怎样找矛盾对并加边呢？

对于一个门上的两把锁，如果这两把锁的钥匙是同一组的，那么任选一个钥匙都可以。

如果是属于不同组的，那么假设这两把钥匙是a1， b1，那么这两组分别是（a1, a2）（b1, b2）， a2和b2是一定不能同时选的，因为选了就没有a1或b1 来打开这个门了

所以<a2,b2>是一个矛盾对，加入边a1->b2, b2->a1

然后题目是要求最多能打开多少个门，那么二分一下最大数量打开门就可以了。

【代码】

#include<iostream>#include<queue>#include<cstdio>#include<cstring>using namespace std; const int MAXN = 2100;const int VN = MAXN*2;const int EN = VN;int n, m; struct Edge{int v, next;}; struct Graph{int size, head[VN];Edge E[EN];void init（）{size=0; memset（head, -1, sizeof（head））;};void addEdge（int u, int v）{E[size].v = v;E[size].next = head[u];head[u] = size++;}}g; class Two_SAT{public:bool check（const Graph& g, const int n）{scc（g, 2*n）;for（int i=0; i<2*n; i+=2）if（belong[i] == belong[i^1]）return false;return true;} private:void tarjan（const Graph& g, const int u）{int v;DFN[u] = low[u] = ++idx;sta[top++] = u;instack[u] = true; for（int e=g.head[u]; e！=-1; e=g.E[e].next）{v = g.E[e].v;if（DFN[v] == -1）{tarjan（g, v）;low[u] = min（low[u], low[v]）;}else if（instack[v]）{low[u] = min（low[u], DFN[v]）; }} if（low[u] == DFN[u]）{++bcnt;do{v = sta[--top];instack[v] = false;belong[v] = bcnt;}while（u ！= v）;}}void scc（const Graph& g, const int n）{idx = bcnt = top = 0;memset（DFN, -1, sizeof（DFN））;memset（instack, 0, sizeof（instack））;for（int i=0; i<n; ++i）if（DFN[i] == -1） tarjan（g, i）;} private:int idx, top, bcnt;int DFN[VN];int low[VN];int belong[VN];int sta[VN];bool instack[VN];}sat; int key[VN];int door[MAXN][2];int idx[VN];int main（）{ while（~scanf（"%d%d", &n, &m） && n+m）{ for（int i=0; i<2*n; ++i）{scanf（"%d", &key[i]）;idx[key[i]] = i;}for（int i=0; i<m; ++i）scanf（"%d%d", &door[i][0], &door[i][1]）; int l=0, r=m+1, mid;int ans = 0;while（l < r）{mid = （l+r）>>1;// 建图g.init（）;for（int i=0; i<mid; ++i）{int a1=door[i][0], b1=door[i][1];int a2=key[idx[a1]^1], b2=key[idx[b1]^1];if（a2 == b1） continue;if（a1==b1） g.addEdge（idx[b1], idx[b1]^1）;else{g.addEdge（idx[a1], idx[b1]^1）;g.addEdge（idx[b1], idx[a1]^1）;}} if（sat.check（g, n））{ans = mid;l=mid+1;}else r=mid;}printf（"%d
", ans）;}return 0;}