POJ3648Wedding(2

POJ 3648 Wedding(2-SAT) http://poj.org/problem?id=3648 题意: 有一对新人结婚,n-1对夫妇去参加婚.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时

POJ 3648 Wedding(2-SAT)

http://poj.org/problem?id=3648

题意:

有一对新人结婚,n-1对夫妇去参加婚礼.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时坐在新娘对面.(只能分开做,或者都坐到新娘一边去)。对于每个输入实例，输出应该坐在新娘同一边的人编号。

分析:

由于有n对夫妇(0号表示新婚夫妻).所以我们这里用0表示第0对的妻子,1表示第0对的丈夫. 2*i表示第i对的夫人,2*i+1表示第i对的丈夫.一共就有2*n个人了.

然后对于每个人来说,把他分成两个节点,如果该人在做左边就mark[i*2],如果该人坐右边就mark[i*2+1].

我令新娘直接坐左边即第0个人mark[0]=true,新郎直接坐右边即第1个人mark[1*2+1]=true.

然后对于每对夫妻,因为他们不能在同一边,所以第i对夫妻中a= 2*i表示妻子,b=2*i+1表丈夫. 有这样的关系:

a在左边,那么b就在右边,a*2->b*2+1

a在右边,那么b就在左边,a*2+1->b*2

b在左边,那么a就在右边,b*2->a*2+1

b在右边,那么a就在左边,b*2+1->a*2

然后对于每对有奸情的人a与b,因为它们不能同时在新娘对面(右边),所以:

a*2+1->b*2

b*2+1->a*2

注意首先我们定了新娘(0号)在左边,新郎(第1号人)一定在右边,所以我们要先加上:

0*2+1->0*2 和 1*2->1*2+1

这样就保证了新娘和新郎在固定的那边不动.

AC代码:

#include
#include
#include
#include
using namespace std;
const int maxn = 1000*2+100;
struct TwoSAT
{
 int n;
 vector G[maxn*2];
 int S[maxn*2],c;
 bool mark[maxn*2];

 bool dfs(int x)
 {
 if(mark[x^1]) return false;
 if(mark[x]) return true;
 mark[x]=true;
 S[c++]=x;
 for(int i=0;in=n;
 for(int i=0;i<2*n;i++) G[i].clear();
 memset(mark,0,sizeof(mark));
 }

 void add_clause(int x,int xval,int y,int yval)
 {
 x=x*2+xval;
 y=y*2+yval;
 G[x].push_back(y);
 }

 bool solve()
 {
 for(int i=0;i<2*n;i+=2)
 if(!mark[i] && !mark[i+1])
 {
 c=0;
 if(!dfs(i))
 {
 while(c>0) mark[S[--c]]=false;
 if(!dfs(i+1)) return false; //注意细节,这里写成了return true;
 }
 }
 return true;
 }
}TS;
int main()
{
 int n,m;
 while(scanf("%d%d",&n,&m)==2)
 {
 if(n==0&&m==0) break;
 TS.init(n*2);
 TS.add_clause(0,1,0,0);//新娘放左
 TS.add_clause(1,0,1,1);//新郎放右
 for(int i=1;i