ACM POJ 2723 Get Luffy Out(2-SAT入門)
17211 ワード
タイトルリンク:http://poj.org/problem?id=2723
【テーマ大意】
2 nは鍵を2つのグループに分けて、あなたに各グループの鍵情報をあげて、そして各グループの鍵は1つしか使えません.
m個のドアがあり、各ドアには2個の鍵があり、1個の鍵を開けるだけでこのドアが開きます.(順番にmゲートに出会う)
最大何個のドアを開けることができるか聞いてください.
【問題解きの考え方】
ドアは順番にしか開けられないので、自然に二分するのがいい選択です.建図の根拠:1、鍵aのペアごとに、bは(a->!b)、(b->!a) つまりa and b=0 aがbで使われていない、あるいはbがaで使われていない、あるいはa,bが使われていない2、ドア対ロックの鍵a,bごとに(!a->b)、(!b->a)つまりa or b=1、aで開くことができてbで開くことができなくて、あるいはbで開くことができてaで開くことができなくて、あるいはaで開くことができてbで開くことができて二分法で解くことができます:
私は次の2つの方法で解いたが,時間はあまり違わなかった.すなわち,強連通成分を解く2つの方法である.
記事の出典:http://www.cnblogs.com/kuangbin/archive/2011/08/24/2152038.html
【テーマ大意】
2 nは鍵を2つのグループに分けて、あなたに各グループの鍵情報をあげて、そして各グループの鍵は1つしか使えません.
m個のドアがあり、各ドアには2個の鍵があり、1個の鍵を開けるだけでこのドアが開きます.(順番にmゲートに出会う)
最大何個のドアを開けることができるか聞いてください.
【問題解きの考え方】
ドアは順番にしか開けられないので、自然に二分するのがいい選択です.建図の根拠:1、鍵aのペアごとに、bは(a->!b)、(b->!a) つまりa and b=0 aがbで使われていない、あるいはbがaで使われていない、あるいはa,bが使われていない2、ドア対ロックの鍵a,bごとに(!a->b)、(!b->a)つまりa or b=1、aで開くことができてbで開くことができなくて、あるいはbで開くことができてaで開くことができなくて、あるいはaで開くことができてbで開くことができて二分法で解くことができます:
私は次の2つの方法で解いたが,時間はあまり違わなかった.すなわち,強連通成分を解く2つの方法である.
/*
POJ 2723 Get Luffy Out
AC
*/
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
const int MAXN=1<<12;
const int MAXM=1<<24;
struct Node
{
int l,r;
}e[MAXN];
struct Node1
{
int from,to,next;
}edge1[MAXM],edge2[MAXM];
int visit1[MAXN],visit2[MAXN],head1[MAXN],head2[MAXN],Belong[MAXN],T[MAXN];
int tol1,tol2,Bcnt,Tcnt;
int hash[MAXN];
void add(int a,int b)
{
edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++;
edge2[tol2].from=b;edge2[tol2].to=a;edge2[tol2].next=head2[b];head2[b]=tol2++;
}
void dfs1(int x)
{
int j;
visit1[x]=1;
for(j=head1[x];j!=-1;j=edge1[j].next)
if(visit1[edge1[j].to]==0) dfs1(edge1[j].to);
T[Tcnt++]=x;
}
void dfs2(int x)
{
int j;
visit2[x]=1;
Belong[x]=Bcnt;
for(j=head2[x];j!=-1;j=edge2[j].next)
if(visit2[edge2[j].to]==0) dfs2(edge2[j].to);
}
int main()
{
int i,j,n,m;
int right,left,mid,ans;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)break;
int a,b;
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
hash[a]=b;
hash[b]=a;
}
for(i=0;i<m;i++)
scanf("%d%d",&e[i].l,&e[i].r);
left=0;
right=m;
while(left<=right)
{
mid=(left+right)/2;
for(i=0;i<4*n;i++)
{
head1[i]=-1;
head2[i]=-1;
visit1[i]=0;
visit2[i]=0;
}
tol1=tol2=0;
Tcnt=Bcnt=0;
for(i=0;i<2*n;i++)
{
add(i,hash[i]+2*n);
}
for(i=0;i<mid;i++)
{
if(e[i].l!=e[i].r)
{
add(e[i].l+2*n,e[i].r);
add(e[i].r+2*n,e[i].l);
}
if(e[i].l==e[i].r)
{
add(e[i].l+2*n,e[i].l);
}
}
for(i=0;i<4*n;i++)
if(!visit1[i]) dfs1(i);
for(i=Tcnt-1;i>=0;i--)
{
if(!visit2[T[i]])
{
dfs2(T[i]);
Bcnt++;
}
}
for(i=0;i<2*n;i++)
{
if(Belong[i]==Belong[i+2*n]) break;
}
if(i>=2*n)
{
ans=mid;left=mid+1;
}
else right=mid-1;
}
printf("%d
",ans);
}
return 0;
} /*
POJ 2723 Get Luffy Out
AC
*/
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
const int MAXN=1<<12;
const int MAXM=1<<24;
int n,m;
struct Node
{
int l,r;
}e[MAXN];
struct Node1
{
int from,to,next;
}edge[MAXM];
int ecnt;
int head[MAXN],Belong[MAXN],Stack[MAXN];
int top,idx,b_cnt;
int hash[MAXN];
int DFN[MAXN],LOW[MAXN];
bool Instack[MAXN];
void add(int a,int b)
{
edge[ecnt].from=a;edge[ecnt].to=b;edge[ecnt].next=head[a];head[a]=ecnt++;
}
void Tarjan(int u)
{
int i,v;
DFN[u]=LOW[u]=(++idx);
Stack[++top]=u;
Instack[u]=true;
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(!DFN[v])
{
Tarjan(v);
if(LOW[u]>LOW[v])LOW[u]=LOW[v];
}
else if(Instack[v]&&LOW[u]>DFN[v])
LOW[u]=DFN[v];
}
if(LOW[u]==DFN[u])
{
b_cnt++;
do
{
v=Stack[top--];
Instack[v]=false;
Belong[v]=b_cnt;
}while(u!=v);
}
}
int solve()
{
int i;
b_cnt=idx=top=0;
for(i=0;i<4*n;i++)
{
DFN[i]=LOW[i]=0;
Belong[i]=0;
Instack[i]=false;
}
for(i=0;i<4*n;i++)
if(!DFN[i]) Tarjan(i);
for(i=0;i<2*n;i++)
{
if(Belong[i]==Belong[i+2*n])
return 0;
}
return 1;
}
int main()
{
int i,j;
int right,left,mid,ans;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)break;
int a,b;
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
hash[a]=b;
hash[b]=a;
}
for(i=0;i<m;i++)
scanf("%d%d",&e[i].l,&e[i].r);
left=0;
right=m;
while(left<=right)
{
mid=(left+right)/2;
for(i=0;i<4*n;i++)
{
head[i]=-1;
}
ecnt=0;
for(i=0;i<2*n;i++)
{
add(i,hash[i]+2*n);
}
for(i=0;i<mid;i++)
{
if(e[i].l!=e[i].r)
{
add(e[i].l+2*n,e[i].r);
add(e[i].r+2*n,e[i].l);
}
if(e[i].l==e[i].r)
{
add(e[i].l+2*n,e[i].l);
}
}
if(solve())
{
ans=mid;left=mid+1;
}
else right=mid-1;
}
printf("%d
",ans);
}
return 0;
} 記事の出典:http://www.cnblogs.com/kuangbin/archive/2011/08/24/2152038.html