算法：POJ 3648 Wedding（2-SAT+输出方案）

算法：POJ 3648 Wedding（2-SAT+输出方案）2014-01-10 csdn shuangde800【题目大意】

有n-1对夫妇被一对新郎新娘邀请来参加婚礼，他们要坐在一条长桌上，可以选择坐在左边或者右边。每对夫妻都不能坐在同一边，他们只能是面对面坐着。

但是这些人中有JQ，共有m对有JQ（新郎也可能有奸情，可怜的新娘...）。要求这些JQ对不能同时坐在新娘的对面。即，每一对JQ 者，他们可以同时坐在和新娘同一边，也可以一个和新娘同一边而另一个在新娘对面即可。

要求找到一种方案并输出，如果没有方案输出bad luck

【思路】

对于每一对夫妇，有两种选择，要么女方和新娘同一边，要么男方和新娘坐在同一边。

然后是根据JQ关系加边。

【代码】

#include<iostream> #include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define WHITE -1#define RED1#define BLUE 0using namespace std;typedef long long int64;const int MAXN = 50;const int VN = MAXN*2;const int EN = VN*VN;int n, m;struct Edge{int u, v, next; };struct Graph{int size, head[VN];Edge E[EN];void init（）{size=0; memset（head, -1, sizeof（head））;};void addEdge（int u, int v）{E[size].u = u; E[size].v = v;E[size].next = head[u];head[u] = size++;}}g, g1;class Two_Sat{public:bool check（const Graph&g, const int n）{scc（g, 2*n）;for（int i=0; i<n; ++i）if（belong[i] == belong[i+n]）return false;return true;}void toposort（const Graph& g, Graph& g1, const int n）{g1.init（）;memset（indeg, 0, sizeof（indeg））;for（int i=0; i<n; ++i）{opp[belong[i]] = belong[i+n];opp[belong[i+n]] = belong[i];}for（int e=0; e<g.size; ++e）{int u = belong[g.E[e].u];int v = belong[g.E[e].v];if（u==v） continue;++indeg[u];g1.addEdge（v, u）;}queue<int>que;memset（color, WHITE, sizeof（color））;for（int i=1; i<=bcnt; ++i）if（！indeg[i]）que.push（i）;while（！que.empty（））{int u = que.front（）; que.pop（）;if（color[u] ！= WHITE） continue;color[u] = RED;color[opp[u]] = BLUE;for（int e=g1.head[u]; e！=-1; e=g1.E[e].next）{int v = g1.E[e].v;if（--indeg[v] == 0）{que.push（v）;}}}// 输出方案printf（"1%c",color[belong[1]]==RED？"w":"h"）;for（int i=2; i<n; ++i）{printf（" %d%c", i, color[belong[i]]==RED？"w":"h"）;}puts（""）;}private:void tarjan（const Graph&g, const int u）{int v;DFN[u] = low[u] = ++idx;sta[top++] = u;instack[u] = true;for（int e=g.head[u]; e！=-1; e=g.E[e].next）{v = g.E[e].v;if（DFN[v] == -1）{tarjan（g, v）;low[u] = min（low[u], low[v]）;}else if（instack[v]）{low[u] = min（low[u], DFN[v]）;}}if（DFN[u] == low[u]）{++bcnt;do{v = sta[--top];instack[v] = false;belong[v] = bcnt;}while（u ！= v）;}}void scc（const Graph& g, const int n）{idx = top = bcnt = 0;memset（DFN, -1, sizeof（DFN））;memset（instack, 0, sizeof（instack））;for（int i=0; i<n; ++i）if（DFN[i] == -1）tarjan（g, i）;}private:int idx, top, bcnt;int DFN[VN], low[VN], belong[VN], sta[VN];bool instack[VN];int color[VN], opp[VN], indeg[VN];}sat;int main（）{char ch1, ch2;int a, b;while（~scanf（"%d%d", &n, &m） && n+m）{g.init（）;g.addEdge（n, 0）; //注意要添加这个！因为新郎也可能有奸情for（int i=0; i<m; ++i）{scanf（"%d%c%d%c",&a,&ch1,&b,&ch2）;if（ch1=="h" && ch2=="h"）{g.addEdge（a, b+n）;g.addEdge（b, a+n）;}else if（ch1=="h" && ch2=="w"）{g.addEdge（a, b）;g.addEdge（b+n, a+n）;}else if（ch1=="w" && ch2=="h"）{g.addEdge（a+n, b+n）;g.addEdge（b, a）;}else if（ch1=="w" && ch2=="w"）{g.addEdge（a+n, b）;g.addEdge（b+n, a）;}}if（！sat.check（g, n）） puts（"bad luck"）;else{sat.toposort（g, g1, n）;}}return 0;}