poj2723-Get Luffy Out

这道题的题意感觉比较难懂。

给出(n)组钥匙，每组钥匙有2把，每组只能选一把钥匙用，有(2n)把锁，每个钥匙对应一把锁。一共有(m)层楼，从0楼开始，进入下一层楼有一道门，门上有两个锁，开任意一个都可以。问最多能够走到多少层。$$nle 2^{10},mle 2^{11}$$.

分析

走到第(x)层必须走到第(x-1)层，有了这个性质，我们可以二分答案。那么如何判断呢？注意到每层楼有两把锁，开一把即可，每组有两把钥匙只能用一把，所以这是一个2-SAT问题。我们可以把每个锁开不开当成变量，同一组的钥匙不能都用，就是两把锁不能都开，也就是(a e b)。每层楼必须开一个锁，就是(a ext{ or } b)。

代码

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
	int x=0,f=1;
	char c=getchar();
	for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
	for (;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int maxn=1<<13|1;
const int maxm=1<<11|1;
struct keys {
	int x,y;
} a[maxn];
struct floor {
	int x,y;
} b[maxm];
struct edge {
	int v,nxt;
};
int n,m,dfn[maxn],low[maxn],dft,id[maxn],col,sta[maxn],top;
bool ins[maxn];
struct graph {
	edge e[maxn*maxn];
	int h[maxn],tot;
	void clear() {
		memset(h,0,sizeof h),tot=0;
	}
	void add(int u,int v) {
		e[++tot]=(edge){v,h[u]};
		h[u]=tot;
	}
	void Tarjan(int x) {
		dfn[x]=low[x]=++dft;
		sta[++top]=x;
		ins[x]=true;
		for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (!dfn[v]) {
			Tarjan(v);
			low[x]=min(low[x],low[v]);
		} else if (ins[v]) low[x]=min(low[x],dfn[v]);
		if (low[x]==dfn[x]) {
			++col;
			do id[sta[top--]]=col; while (sta[top+1]!=x);
		}
		ins[x]=false;
	}
} A;
bool ok(int fl) {
	A.clear();
	memset(id,0,sizeof id),memset(low,0,sizeof low),memset(dfn,0,sizeof dfn);
	dft=col=top=0;
	int ader=n<<1;
	for (int i=1;i<=fl;++i) A.add(b[i].x+ader,b[i].y),A.add(b[i].y+ader,b[i].x);
	for (int i=1;i<=n;++i) A.add(a[i].x,a[i].y+ader),A.add(a[i].y,a[i].x+ader),A.add(a[i].x+ader,a[i].y),A.add(a[i].y+ader,a[i].x);
	for (int i=1;i<=ader;++i) if (!dfn[i]) A.Tarjan(i);
	for (int i=1;i<=ader;++i) if (id[i]==id[i+ader]) return false;
	return true;
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
#endif
	while (~scanf("%d%d",&n,&m) && !(n==0 && m==0)) {
		for (int i=1;i<=n;++i) a[i].x=read()+1,a[i].y=read()+1;
		for (int i=1;i<=m;++i) b[i].x=read()+1,b[i].y=read()+1;
		int l=0,r=m,mid,ans=0;
		while (l<=r) {
			mid=l+r>>1;
			if (ok(mid)) ans=mid,l=mid+1; else r=mid-1;
		}
		printf("%d
",ans);
	}
	return 0;
}