2-SAT——4.0(poj2723 Get Luffy Out)
poj2723 Get Luffy Out
タイトル:n対の鍵を与えて、ペアごとに1本だけ選んで使うことができて、1本ごとに1回しか使うことができなくて、1対の鍵の中の1本が使用された後に、もう1本も使うことができません;それからmドアを与えて、各ドアには2つの鍵が開いていて、最大何本のドアを開けることができますか(与えられた順序で開くことができます).
矛盾関係:
1:n鍵のうち、AとBは1本しか選択できず、点Aで選択鍵Aを表し、Aで選択しない(同理用点BとB‘で鍵Bの選択関係を表す)、建辺(A->B’)で鍵Aで鍵Bを使えないことを表し、また(B->A')でBを使えばAを使えないことを表す.
2:mゲートは、各ペアに2つの鍵が開くことができ(CとDと仮定)、可能な選択は(CでDを使わない)、または(DでCを使わない)、この関係に基づいてエッジ(D'->C)、(C'->D)を構築します.
(PS:上の2ステップ目の(CでDを使わない)と(DでCを使わない)エッジを作ると(C->D')、(D->C')間違いです.このように建辺は2-SAT問題の建辺ルールに違反していませんね.しかし、最後に、このように建辺すれば、図の中のすべての辺がXからXを指していることに気づきました.それに強いつながりを求めるのは意味がありません.具体的には、その神牛路が時代遅れなので、説明してください.感謝に堪えません)
図を作成したら、2点列挙の答えを考えることができます.
タイトル:n対の鍵を与えて、ペアごとに1本だけ選んで使うことができて、1本ごとに1回しか使うことができなくて、1対の鍵の中の1本が使用された後に、もう1本も使うことができません;それからmドアを与えて、各ドアには2つの鍵が開いていて、最大何本のドアを開けることができますか(与えられた順序で開くことができます).
矛盾関係:
1:n鍵のうち、AとBは1本しか選択できず、点Aで選択鍵Aを表し、Aで選択しない(同理用点BとB‘で鍵Bの選択関係を表す)、建辺(A->B’)で鍵Aで鍵Bを使えないことを表し、また(B->A')でBを使えばAを使えないことを表す.
2:mゲートは、各ペアに2つの鍵が開くことができ(CとDと仮定)、可能な選択は(CでDを使わない)、または(DでCを使わない)、この関係に基づいてエッジ(D'->C)、(C'->D)を構築します.
(PS:上の2ステップ目の(CでDを使わない)と(DでCを使わない)エッジを作ると(C->D')、(D->C')間違いです.このように建辺は2-SAT問題の建辺ルールに違反していませんね.しかし、最後に、このように建辺すれば、図の中のすべての辺がXからXを指していることに気づきました.それに強いつながりを求めるのは意味がありません.具体的には、その神牛路が時代遅れなので、説明してください.感謝に堪えません)
図を作成したら、2点列挙の答えを考えることができます.
#include<cstdio>
#include<cstring>
#include<stack>
#include<climits>
using namespace std;
const int N = 4100;
struct Edge{
int s,e,next;
}edge[3*N];
int n,m,e_num,vis_num,cnt,head[N],instack[N],low[N],tim[N],belong[N];
void AddEdge(int a,int b){
edge[e_num].s=a; edge[e_num].e=b; edge[e_num].next=head[a]; head[a]=e_num++;
}
stack <int>st;
void tarjan(int x){
int i;
tim[x]=low[x]=++vis_num;
instack[x]=1;
st.push(x);
for(i=head[x];i!=-1;i=edge[i].next){
int u=edge[i].e;
if(tim[u]==-1){
tarjan(u);
if(low[x]>low[u])low[x]=low[u];
}
else if(instack[u] && low[x]>tim[u])low[x]=tim[u];
}
if(low[x]==tim[x]){
cnt++;
do{
i=st.top();
st.pop();
instack[i]=0;
belong[i]=cnt;
}while(i!=x);
}
}
void init(){
vis_num=cnt=0;
memset(instack,0,sizeof(instack));
memset(belong,-1,sizeof(belong));
memset(tim,-1,sizeof(tim));
memset(low,0,sizeof(low));
}
int main()
{
int i,left,right,mid,ans;
int a[2][N],x[N],y[N];
while(scanf("%d%d",&n,&m),n+m)
{
memset(x,-1,sizeof(x));
memset(y,-1,sizeof(y));
for(i=0;i<n;i++)//2*i 2*i+1 i i
scanf("%d%d",&x[i],&y[i]);
for(i=0;i<m;i++)
scanf("%d%d",&a[0][i],&a[1][i]);
left=0; right=m;
while(left<=right){
e_num=0;
memset(head,-1,sizeof(head));
for(i=0;i<n;i++){//2*i 2*i+1 i i
AddEdge(2*x[i],2*y[i]+1);
AddEdge(2*y[i],2*x[i]+1);
}
mid=(left+right)/2;
for(i=0;i<mid;i++){
AddEdge(2*a[0][i]+1,2*a[1][i]);
AddEdge(2*a[1][i]+1,2*a[0][i]);
}
init();
for(i=0;i<4*n;i++){
if(tim[i]==-1)tarjan(i);
}
int flag=1;
for(i=0;i<2*n;i++){
if(belong[2*i]==belong[2*i+1]){
flag=0;break;
}
}
if(flag){
ans=mid; left=mid+1;
}
else right=mid-1;
}
printf("%d
",ans);
}
return 0;
}