[POJ 2723] 二分枚举、2-SAT判定

【题目大意】 有m道门, 开了前一道才能开后一道, 每道门上两把锁, 开一把就能开门, 这些锁并不是完全不同. 有2n把不同的钥匙, 每把对应一种锁, 这些钥匙被分成n对, 每对钥匙只能取其中的一把, 取其中一把, 另一把就会消失, 问最多能开几道门.

【算法分析】对每个类型的钥匙，拆成两个点，分别表示用这把钥匙和不用这把钥匙。然后二分答案，再利用题中的条件构造有向图，2-SAT判断就行了。

【其它】1A
6398374 edward2 2723 Accepted 860K 32MS G++ 1959B 2010-02-01 22:26:05
【CODE】
#include #include #include #define N 1<<18
struct edge{int y,next;}g[1000000];
int n,m,e,ls[N],need[2][N],op[N],f[N],dep[N],color[N];

void init(){
for (int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
op[x]=y;
op[y]=x;
}
for (int i=1;i<=m;i++) scanf("%d%d",&need[0][i],&need[1][i]);
}

int gf(int k){
if (f[k]==k) return k;
f[k]=gf(f[k]);
return f[k];
}

void dfs(int k){
for (int t=ls[k];t;t=g[t].next)
if (!dep[g[t].y]){
dep[g[t].y]=dep[k]+1;
dfs(g[t].y);
if (dep[gf(g[t].y)] }
else if (!color[gf(g[t].y)] && dep[gf(g[t].y)] f[k]=f[g[t].y];
color[k]=1;
}

void tarjan(){
for (int i=0;i<4*n;i++){
dep[i]=0;
f[i]=i;
color[i]=0;
}
for (int i=0;i<4*n;i++)
if (!dep[i]){
dep[i]=1;
dfs(i);
}
for (int i=0;i<4*n;i++) gf(i);
}

inline void add(int x,int y){
e++;
g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

bool flag(int k){
if (k==0) return true;
e=0; for (int i=0;i<4*n;i++) ls[i]=0;
for (int i=0;i<2*n;i++){
add(i,op[i]+2*n);
add(i+2*n,op[i]);
}
for (int i=1;i<=k;i++){
add(need[0][i],need[1][i]+2*n);
add(need[1][i],need[0][i]+2*n);
}
tarjan();
for (int i=0;i<2*n;i++)
if (f[i]==f[i+2*n]) return false;
return true;
}

void work(){
int l=0,r=m,mid;
while (l+1 mid=(l+r)/2;
if (flag(mid)) l=mid;
else r=mid-1;
}
if (flag(r)) printf("%dn",r);
else printf("%dn",l);
}

int main(){
for (;;){
scanf("%d%d",&n,&m);
if (n+m==0) break;
init();
work();
}
return 0;
}