题意:

　　有N-1对夫妻参加一个婚宴，所有人都坐在一个长长的餐桌左侧或者右侧，新郎和新娘面做面坐在桌子的两侧。由于新娘的头饰很复杂，她无法看到和她坐在同一侧餐桌的人，只能看到对面餐桌的人。任意一对夫妻不能坐在桌子的同侧，另外有m对人吵过架，而新娘不希望看到两个吵过架的人坐在他的对面，问如何安排这些座位。

 

分析：

　　考虑新娘对面那一边，吵过架的不能坐在一起。两夫妻中只能选一个而且必须选一个坐在新娘对面，但不能选两个吵过架的人。所以我们可以用人物关系建图，然后用2-SAT求解。

　　另外，说一下2-SAT的不回溯算法，是在图对称的时候才保证正确性的。所以记得保证图是对称的哦。

 

 

代码如下：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define Maxn 2010 8 #define Maxm 1000010 9 10 int n,m;11 int first[Maxn];12 bool mark[Maxn];13 int s[Maxn],sl;14 15 struct node16 {17     int x,y,next;18 }t[Maxm];int len;19 20 void ins(int x,int y)21 {22     t[++len].x=x;t[len].y=y;23     t[len].next=first[x];first[x]=len;24 }25 26 bool dfs(int x)27 {28     if(mark[x^1]) return 0;29     if(mark[x]) return 1;30     mark[x]=1;31     s[++sl]=x;32     for(int i=first[x];i;i=t[i].next)33     {34         if(!dfs(t[i].y)) return 0;35     }36     return 1;37 }38 39 bool ffind()40 {41     memset(mark,0,sizeof(mark));42     mark[0]=1;43     if(!dfs(0)) return 0;44     for(int i=1;i
          
         
        
       
      

 

2016-03-24 13:24:20