題目鏈接：

題目

建圖：

1.新娘向新郎連邊，表示選取的時候選取新娘對面的。

2.

有奸情的人比如是 xh yh那么連邊(x,y+n)以及(y,x+n)

如果是xh yw?那么連邊(x,y)?以及 (y+n,x)

如果是xw yh?那么連邊(x+n,y+n)以及(y,x)

如果是xw yw那么連邊(x+n,y)以及(y,x+n)

其中? (x表示丈夫 x <= n ，x+n表示妻子)

3.跑2-sat，輸出的時候注意輸出新娘一邊的。

因為我們選取的時候是按照新郎一邊的選擇的，所以說輸出的時候要取反再輸出。

代碼：

#include <vector> #include <cstring> #include <cstdio> #include <queue> using namespace std; const int maxn = 1000; int head[maxn]; int DFN[maxn],LOW[maxn],stk[maxn],visit[maxn],belong[maxn]; vector<int> scc[maxn]; int tot,idx,cnt,sccnum; int n,color[maxn],degree[maxn],pos[maxn]; struct Es{ int v; int next; int cost; }Es[maxn<<1]; vector<int> bkG[maxn]; void init(){ sccnum = tot = idx = cnt = 0; memset(head,-1,sizeof(head)); memset(DFN,0,sizeof(DFN)); memset(LOW,0,sizeof(LOW)); memset(visit,0,sizeof(visit)); memset(color,0,sizeof(color)); memset(degree,0,sizeof(degree));memset(pos,0,sizeof(pos));for(int i = 0;i < maxn;i++) scc[i].clear();for(int i = 0;i < maxn;++i) bkG[i].clear(); } inline void add_edge(int i,int j,int cost = 1){ Es[cnt].v = j; Es[cnt].cost = cost; Es[cnt].next = head[i]; head[i] = cnt++; } void tarjan(int x) {DFN[x]=LOW[x]=++tot;stk[++idx]=x;visit[x]=1;for(int i=head[x];i!=-1;i=Es[i].next){if(!DFN[Es[i].v]) {tarjan(Es[i].v);LOW[x] = min(LOW[x],LOW[Es[i].v]);}else if(visit[Es[i].v ]){ LOW[x] = min(LOW[x],DFN[Es[i].v]);}}if(LOW[x]==DFN[x]){++sccnum;do{int item = stk[idx];belong[item] = sccnum;scc[sccnum].push_back(item);visit[item]=0;idx--;}while(x!=stk[idx+1]);}return ; } bool check(){for(int i = 1;i <= n;i++){if(belong[i] == belong[i+n]) return false;}return true; } bool solve(){for(int i = 1;i <= 2*n;++i )if(!DFN[i]) tarjan(i);if(!check()) return false;for(int i = 1;i <= n;++i){if(!pos[belong[i]]){pos[belong[i]] = belong[i+n];pos[belong[i+n]] = belong[i];}}for(int i = 1;i <= 2*n;++i){for(int e = head[i];e != -1;e = Es[e].next){int v = Es[e].v;if(belong[i] != belong[v]){degree[belong[i]]++;bkG[belong[v]].push_back(belong[i]);}}}queue<int> que;for(int i = 1;i <= sccnum;++i){if(!degree[i])que.push(i);}while(!que.empty()){int u = que.front();que.pop();if(!color[u]){color[u] = 1;color[pos[u]] = 2;}for(int i = 0;i < bkG[u].size();++i){int v = bkG[u][i];degree[v]--;if(!degree[v])que.push(v);}}//在這里準備輸出答案//為1表示選中，為2表示為選中/*for(int i = 1;i <= n;++i){if(color[belong[i]] == 1) {//Yes}else{//No}} */return true; } int main(){int m;while(~scanf("%d%d",&n,&m) && n + m){init();//n--;for(int i = 0;i < m;++i){int a = 0,b = 0;char ta,tb;scanf("%d%c%d%c",&a,&ta,&b,&tb);a++;b++;add_edge(ta == 'h'?a:a+n,tb == 'h'?b+n:b);add_edge(tb == 'h'?b:b+n,ta == 'h'?a+n:a);}add_edge(n+1,1);if(solve()){for(int i = 2;i <= n;i++){if(color[belong[i]] == 1){printf("%d%c ",i-1,'w');}else{printf("%d%c ",i-1,'h');}}puts("");}else{puts("bad luck");}}} /* 3 2 1w 2w 1w 2h*/

總結

以上是生活随笔為你收集整理的poj3648 Wedding 2-sat的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。