[読み込み]ACM POJ 3648 Wedding(2-SAT入門)
21979 ワード
タイトルリンク:http://poj.org/problem?id=3648
著者:kuangbin
(転載は出典を明記してください、ブログ:www.cnblogs.com/kuangbin)
【題目大意】新人カップルの結婚式には多くのカップルが参加します.それぞれ長いテーブルの両側に行います.新郎新婦はそれぞれ両側に座り、新婦は彼女の向こうの人しか見えません.新婦は彼女の向こうに夫婦がいるのを見たくありません.
しかも奸通関系にある人もいれば(男の人と男の人がいて、女の人と男の人、女の人と女の人がいて、その上新郎も他の人と奸通関系があるかもしれません)、新妇は奸通関系のあるカップルを见たくありません.
つまり姦通関係のある人は一緒に花嫁の向こうに座ってはいけない.
入力は:_nカップル(新郎新婦の在女を含めて0-(n-1)、新郎、新婦のペアの番号は0)、_mペアの姦通関係です.
次に_m行は姦通関係があります.hは男を表し、w表は女を表し、3 w 5 hは3組目の夫婦の女を表し、5組目の夫婦の男を表します.
【タイトルカテゴリ】2-SAT
【テーマ分析】新郎を含む半数が新婦の向かいに座り、夫婦がいてはならず、姦通関係がないカップルを選ぶ.
番号はそれぞれ0-2*_nで、奇数は男で、偶数は女です.自然0は新婦で、1は新郎です.
必ず1を选ぶために、辺0->1をプラスして、花嫁を选ぶと必ず新郎を选ぶので、判断が间违います.
新郎も含めて選ばれたに違いない.
注意したいのは、出力するときは花嫁と同じ側に座る人です.つまり、逆に出力すればいいのです.
コード:
記事の出典:http://www.cnblogs.com/kuangbin/archive/2011/08/22/2149667.html
著者:kuangbin
(転載は出典を明記してください、ブログ:www.cnblogs.com/kuangbin)
【題目大意】新人カップルの結婚式には多くのカップルが参加します.それぞれ長いテーブルの両側に行います.新郎新婦はそれぞれ両側に座り、新婦は彼女の向こうの人しか見えません.新婦は彼女の向こうに夫婦がいるのを見たくありません.
しかも奸通関系にある人もいれば(男の人と男の人がいて、女の人と男の人、女の人と女の人がいて、その上新郎も他の人と奸通関系があるかもしれません)、新妇は奸通関系のあるカップルを见たくありません.
つまり姦通関係のある人は一緒に花嫁の向こうに座ってはいけない.
入力は:_nカップル(新郎新婦の在女を含めて0-(n-1)、新郎、新婦のペアの番号は0)、_mペアの姦通関係です.
次に_m行は姦通関係があります.hは男を表し、w表は女を表し、3 w 5 hは3組目の夫婦の女を表し、5組目の夫婦の男を表します.
【タイトルカテゴリ】2-SAT
【テーマ分析】新郎を含む半数が新婦の向かいに座り、夫婦がいてはならず、姦通関係がないカップルを選ぶ.
番号はそれぞれ0-2*_nで、奇数は男で、偶数は女です.自然0は新婦で、1は新郎です.
必ず1を选ぶために、辺0->1をプラスして、花嫁を选ぶと必ず新郎を选ぶので、判断が间违います.
新郎も含めて選ばれたに違いない.
注意したいのは、出力するときは花嫁と同じ側に座る人です.つまり、逆に出力すればいいのです.
コード:
/*
POJ3648
*/
#include<iostream>
#include<stdio.h>
using namespace std;
const int MAXN=20000;
const int MAXM=100000;//
struct Node
{
int a,b,pre,next;
}E[MAXM],E2[MAXM];//
int _n,n,m,V[MAXN],ST[MAXN][2],Q[MAXN],Q2[MAXN],vst[MAXN];
bool res_ex;
void init_d()//
{
for(int i=0;i<n;i++)//
E[i].a=E[i].pre=E[i].next=E2[i].a=E2[i].pre=E2[i].next=i;
m=n;//m
}
void add_edge(int a,int b)// (a,b),
{//
E[m].a=a;E[m].b=b;E[m].pre=E[a].pre;E[m].next=a;E[a].pre=m;E[E[m].pre].next=m;
E2[m].a=b;E2[m].b=a;E2[m].pre=E2[b].pre;E2[m].next=b;E2[b].pre=m;E2[E2[m].pre].next=m++;
}
void solve()
{
for(int i=0;i<n;i++)
{
V[i]=0;
vst[i]=0;
}
res_ex=1;
int i,i1,i2,j,k,len,front,rear,front2,rear2;
bool ff;
for(int _i=0;_i<_n;_i++)
{
if(V[_i<<1]==1||V[(_i<<1)+1]==1) continue;//
i=_i<<1;len=0;
if(!V[i])
{
ST[len][0]=i;ST[len++][1]=1;
if(!V[i ^ 1])
{
ST[len][0]=i^1;
ST[len++][1]=2;
}
Q[front=rear=0]=i;
vst[i]=i1=n+i;
Q2[front2=rear2=0]=i^1;
vst[i^1]=i2=(n<<1)+i;
//i1,i2 ， ，
ff=1;
for(;front<=rear;front++)
{
j=Q[front];
for(int p=E[j].next;p!=j;p=E[p].next)
{
k=E[p].b;
if(V[k]==2||vst[k]==i2||V[k^1]==1||vst[k^1]==i1)
{ff=0;break;}
if(vst[k]!=i1)
{
Q[++rear]=k;vst[k]=i1;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=1;
}
}
if(vst[k^1]!=i2)
{
Q2[++rear2]=k^1;vst[k^1]=i2;
if(!V[k])
{
ST[len][0]=k^1;
ST[len++][1]=2;
}
}
}
if(!ff) break;
}
if(ff)
{
for(;front2<=rear2;front2++)
{
j=Q2[front2];
for(int p=E2[j].next;p!=j;p=E2[p].next)
{
k=E2[p].b;
if(V[k]==1||vst[k]==i1)
{
ff=0;
break;
}
if(vst[k]!=i2)
{
vst[k]=i2;Q2[++rear]=k;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=2;
}
}
}
if(!ff) break;
}
if(ff)
{
for(int j=0;j<len;j++) V[ST[j][0]]=ST[j][1];
continue;
}
}
}
i=(_i<<1)+1;len=0;
if(!V[i])
{
ST[len][0]=i;ST[len++][1]=1;
if(!V[i ^ 1])
{
ST[len][0]=i^1;
ST[len++][1]=2;
}
Q[front=rear=0]=i;
vst[i]=i1=n+i;
Q2[front2=rear2=0]=i^1;
vst[i^1]=i2=(n<<1)+i;
ff=1;
for(;front<=rear;front++)
{
j=Q[front];
for(int p=E[j].next;p!=j;p=E[p].next)
{
k=E[p].b;
if(V[k]==2||vst[k]==i2||V[k^1]==1||vst[k^1]==i1)
{ff=0;break;}
if(vst[k]!=i1)
{
Q[++rear]=k;vst[k]=i1;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=1;
}
}
if(vst[k^1]!=i2)
{
Q2[++rear2]=k^1;vst[k^1]=i2;
if(!V[k])
{
ST[len][0]=k^1;
ST[len++][1]=2;
}
}
}
if(!ff) break;
}
if(ff)
{
for(;front2<=rear2;front2++)
{
j=Q2[front2];
for(int p=E2[j].next;p!=j;p=E2[p].next)
{
k=E2[p].b;
if(V[k]==1||vst[k]==i1)
{
ff=0;
break;
}
if(vst[k]!=i2)
{
vst[k]=i2;Q2[++rear]=k;
if(!V[k])
{
ST[len][0]=k;
ST[len++][1]=2;
}
}
}
if(!ff) break;
}
if(ff)
{
for(int j=0;j<len;j++) V[ST[j][0]]=ST[j][1];
continue;
}
}
}
if(V[_i<<1]+V[(_i<<1)+1]!=3){res_ex=0;break;}
}
}
int main()
{
int _m,a,b;
char ch1,ch2;
while(scanf("%d%d",&_n,&_m)!=EOF)//_n ，_m
{
if(_n==0&&_m==0)break;
n=_n<<1;
init_d();
for(int i=0;i<_m;i++)
{
scanf("%d%c%d%c",&a,&ch1,&b,&ch2);
if(ch1=='w') a=2*a;
else a=2*a+1;
if(ch2=='w') b=2*b;
else b=2*b+1;
if(a!=(b^1))
{
add_edge(a,b^1);// a, b^1，
add_edge(b,a^1);// b, a^1，
}
}
add_edge(0,1);// 。
// ， 。
// ，
solve();
bool first=false;
if(res_ex)
{
for(int i=0;i<n;i++)
{
if(V[i]==1&&i!=1)
{
if(first)printf(" ");
else first=true;
printf("%d%c",i/2,i%2==0?'h':'w');// ，
// h w
}
}
printf("
");
}
else printf("bad luck
");
}
return 0;
} 記事の出典:http://www.cnblogs.com/kuangbin/archive/2011/08/22/2149667.html