这道题的意思是给你n对钥匙， 编号0 - 2*n-1, 有m对门每个门后面有两个锁一个钥匙只能开一把锁， 并且一对钥匙中如果使用了一把锁， 那么另外一把就不能再使用，每个门后面的锁可能会一样， 根据钥匙我们可以发现这是个2-sat问题，门告诉我们那两个钥匙不能共存， 如果门后面的锁一样的话则必须选择这个钥匙， 代码如下：
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn = (1<<11)+100; int N, M; struct Key { int a, b; }ke[maxn]; int f[maxn]; struct Door { int a, b; }Do[maxn]; struct Scc { int V; vector<int> G[maxn]; //原始图 vector<int> rG[maxn]; //反向边 vector<int> vs; //后序遍历顶点列表 bool used[maxn]; //访问标记 int cmp[maxn]; //所属强连通分量 void init() { for(int i=0; i<=V; i++) G[i].clear(), rG[i].clear(); } void add_edge(int from, int to) { G[from].push_back(to); rG[to].push_back(from); } void dfs(int v) { used[v] = true; for(int i=0; i<G[v].size(); i++) if(!used[G[v][i]]) dfs(G[v][i]); vs.push_back(v); } void rdfs(int v, int k) { used[v] = true; cmp[v] = k; for(int i=0; i<rG[v].size(); i++) if(!used[rG[v][i]]) rdfs(rG[v][i], k); } int scc() { memset(used, 0, sizeof(used)); vs.clear(); for(int v=1; v<=V; v++) if(!used[v]) dfs(v); memset(used, 0, sizeof(used)); int k = 1; for(int i=vs.size()-1; i>=0; i--) if(!used[vs[i]]) rdfs(vs[i], k++); return k-1; } }ss; bool check(int mid) { ss.V = 2*N; ss.init(); for(int i=0; i<mid; i++) if(Do[i].a != Do[i].b) //不一样时的情况 { ss.add_edge(Do[i].a, f[Do[i].b]); ss.add_edge(Do[i].b, f[Do[i].a]); } else ss.add_edge(f[Do[i].a], Do[i].a); //一样的时候必须选 ss.scc(); bool res = true; for(int i=0; i<N; i++) { int u=ke[i].a, v=ke[i].b; if(ss.cmp[u]==ss.cmp[v]) { res = false; break; } } return res; } int main() { while(scanf("%d%d", &N, &M)==2) { if(N==0 && M==0) break; for(int i=0; i<N; i++) { int a, b; scanf("%d%d", &a, &b); f[a] = b; f[b] = a; ke[i] = (Key){a, b}; } for(int i=0; i<M; i++) { int a, b; scanf("%d%d", &a, &b); Do[i] = (Door){a, b}; } int l=0, r=M; int ans; while(l <= r) { int mid = (l+r)/2; bool tp = check(mid); //printf("l=%d, r=%d, mid=%d, tp=%d ", l, r, mid, tp); if(tp) { ans = mid; l = mid+1; } else r = mid-1; } printf("%d ", ans); } return 0; }