对于每组钥匙，设编号为i,j，则 i&&j=0 添加边(i,~j),(j,~i)
对于每扇门，设开他的钥匙编号为i,j，则 iVj=1(i||j) 添加边(~i,j),(~j,i)
然后二分答案就可以了，能开i扇门，则小于i的门都能开
代码：
#include<iostream> #include<stack> using namespace std; const int MAX=4500; struct node { int v,next; }g[MAX*MAX]; int dfn[MAX],adj[MAX],low[MAX],inStack[MAX],bel[MAX],pp[MAX][2]; int x[MAX],y[MAX]; int e,n,m,index,cnt; stack<int>s; void add(int u,int v) { g[e].v=v; g[e].next=adj[u]; adj[u]=e++; } void tarjan(int u) { dfn[u]=low[u]=++index; s.push(u); inStack[u]=1; int i,v; for(i=adj[u];i!=-1;i=g[i].next) { v=g[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(inStack[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { cnt++; do { v=s.top(); s.pop(); inStack[v]=0; bel[v]=cnt; }while(u!=v); } } int solve(int t) { memset(dfn,0,sizeof(dfn)); memset(adj,-1,sizeof(adj)); e=cnt=index=0; for(int i=1;i<=n;i++) { add(2*pp[i][0],2*pp[i][1]+1); add(2*pp[i][1],2*pp[i][0]+1); } for(int i=1;i<=t;i++) { add(2*x[i]+1,2*y[i]); add(2*y[i]+1,2*x[i]); } while(!s.empty()) s.pop(); memset(inStack,0,sizeof(inStack)); for(int i=0;i<4*n;i++) { if(!dfn[i]) tarjan(i); } for(int i=0;i<2*n;i++) { if(bel[2*i]==bel[2*i+1]) return 0; } return 1; } int main() { int i,j; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; for(i=1;i<=n;i++) { scanf("%d%d",&pp[i][0],&pp[i][1]); } for(i=1;i<=m;i++) { scanf("%d%d",&x[i],&y[i]); } int mid,ans=0,l=1,r=m; while(l<=r) { mid=(l+r)/2; if(solve(mid)) { ans=mid; l=mid+1; } else r=mid-1; } cout<<ans<<endl; } return 0; }
