題意:
有2*n把鑰匙配成n對,每對中只能使用一把,另外有m道門,每道門能被2把藥匙打開,問最多能從1開始按順序打開多少道門。
分析:
二分枚舉能打開的門數,用2-sat算法判斷能否打開。
代碼:
//poj 2723 //sep9 #include#include #include #include using namespace std; const int maxN=10024; const int maxM=100024; int e,n,m,t,ecnt; int head[maxN],ins[maxN],low[maxN],dfn[maxN]; int sol[maxN],belong[maxN]; stack s; struct Edge { int v,next; }edge[maxM]; struct Door { int x,y; }door[maxM]; struct Lock { int x,y; }lock[maxN]; void addegde(int u,int v) { edge[e].v=v;edge[e].next=head[u]; head[u]=e++; } void dfs(int x) { low[x]=dfn[x]=++t; s.push(x); ins[x]=1; for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].v; if(!dfn[v]){ dfs(v); low[x]=min(low[x],low[v]); }else if(ins[v]==1) low[x]=min(low[x],dfn[v]); } if(dfn[x]==low[x]){ ++ecnt; int k; do{ k=s.top(); s.pop(); ins[k]=0; belong[k]=ecnt; }while(dfn[k]!=low[k]); } } int two_sat() { memset(ins,0,sizeof(ins)); memset(dfn,0,sizeof(dfn)); while(!s.empty()) s.pop(); int i; t=0,ecnt=0; for(i=1;i<=2*n;++i) if(!dfn[i]) dfs(i); for(i=1;i<=n;++i) if(belong[i]==belong[i+n]) return 0; return 1; } int pass(int mid) { if(mid==0) return 1; int i; e=0; memset(head,-1,sizeof(head)); for(i=1;i<=n;++i){ int a=lock[i].x; int b=lock[i].y; addegde(a,b+n); addegde(b,a+n); } for(i=1;i<=mid;++i){ int a=door[i].x; int b=door[i].y; addegde(a+n,b); addegde(b+n,a); } return two_sat(); } int main() { while(scanf("%d%d",&n,&m)==2){ if(m==0&&n==0) break; int i; for(i=1;i<=n;++i){ scanf("%d%d",&lock[i].x,&lock[i].y); ++lock[i].x; ++lock[i].y; } n*=2; for(i=1;i<=m;++i){ scanf("%d%d",&door[i].x,&door[i].y); ++door[i].x; ++door[i].y; } int l=0,r=m+1; while(l