poj3648 2-sat 输出任意一组解

题意：
      一对夫妻结婚，请来了n对夫妻，所有人坐在同一张桌子上吃饭，这张桌子是长方形的可以坐两排人，有如下限制
（1） 新娘和新郎不做同一侧。
（2） 每对来的夫妻也不能坐在同一侧。 
（3） 有一些人有暧昧关系（男女，男男，或者女女），有暧昧关系的两

个人不可以同时坐在新娘对面。

输出一组可行解，输出的是坐在新娘对面的人。


思路：

     根据限制关系，而且还是二选一，显然这个是2sat,对于每个人，都拆成两个点，一个是a表示坐在新娘这一侧，另一个是~a表示坐在新郎这一侧，则对于任何有暧昧关系的，要么一边坐一个，要不同时坐在新娘这一侧，则只要他们两个中至少有一个1就行了，建图是这样 ~a -> b ,~b -> a,对于每一对，他们不能坐在同一侧则不能相同，建图是 a -> ~b ,b -> ~a ,~a ->b ,~b -> a ,还有就是新娘必须坐在新娘这侧，直接 ~a -> a.

#include<stdio.h> #include<string.h> #include<stack>#define N_node 5000 #define N_edge 100000 #define R 1 #define B 2using namespace std;typedef struct {int to ,next; }STAR;STAR E1[N_edge] ,E2[N_edge]; int list1[N_node] ,list2[N_node] ,tot; int Belong[N_node] ,cnt; int mark[N_node] ,Col[N_node]; stack<int>st ,stt;void add(int a ,int b) {E1[++tot].to = b;E1[tot].next = list1[a];list1[a] = tot;E2[tot].to = a;E2[tot].next = list2[b];list2[b] = tot; }void DFS1(int s) {mark[s] = 1;for(int k = list1[s] ;k ;k = E1[k].next)if(!mark[E1[k].to]) DFS1(E1[k].to);st.push(s) ,stt.push(s); }void DFS2(int s) {mark[s] = 1;Belong[s] = cnt;for(int k = list2[s] ;k ;k = E2[k].next)if(!mark[E2[k].to]) DFS2(E2[k].to); }bool solve(int n) {memset(mark ,0 ,sizeof(mark));while(!st.empty()) st.pop();while(!stt.empty()) stt.pop();for(int i = 0 ;i < 4 * n ;i ++)if(!mark[i]) DFS1(i);memset(mark ,0 ,sizeof(mark)) ,cnt = 0;while(!st.empty()){int xin = st.top();st.pop();if(mark[xin]) continue;cnt ++;DFS2(xin);}for(int i = 0 ;i < n * 4 ;i += 2)if(Belong[i] == Belong[i^1]) return 0;return 1; }int main () {int i ,n ,m ,a ,b;char c1 ,c2;while(~scanf("%d %d" ,&n ,&m) && n + m){memset(list1 ,0 ,sizeof(list1));memset(list2 ,0 ,sizeof(list2)) ,tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d%c%d%c" ,&a ,&c1 ,&b ,&c2);a = a * 2 + (c1 == 'h' ? 1 : 0);b = b * 2 + (c2 == 'h' ? 1 : 0);add(a * 2 + 1 ,b * 2);add(b * 2 + 1 ,a * 2);} for(i = 0 ;i < n ;i ++){a = i * 2 ,b = i * 2 + 1;add(a * 2 + 1 ,b * 2) ,add(b * 2 + 1 ,a * 2);add(a * 2 ,b * 2 + 1) ,add(b * 2 ,a * 2 + 1);}add(1 ,0);if(!solve(n)){printf("bad luck\n");continue;}memset(Col ,0 ,sizeof(Col));while(!stt.empty()){i = stt.top() ,stt.pop();if(Col[i]) continue;Col[i] = B ,Col[i^1] = R;}int mk = 0;for(i = 4 ;i < n * 4 ;i += 2){ if(Col[i] == B) continue;if(mk) printf(" ");mk = 1;printf("%d" ,i / 4);i % 4 > 1 ? printf("h") : printf("w");}puts("");}return 0; }

总结

以上是生活随笔为你收集整理的poj3648 2-sat 输出任意一组解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。