本文共 1940 字，大约阅读时间需要 6 分钟。
【题目链接】
【题目大意】
有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 #include #include #include 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 >1; // 建图 g.init(); for(int i=0; i
转载地址：http://npzni.baihongyu.com/