题目链接：http://poj.org/problem?id=3648
题意：有n对夫妻坐成两排，其中第0对为新娘新郎。有m对奸情，新娘不愿意看到对面排存在奸情，问是否有合理方案，有输出一组解，否则输出"bad luck";
思路：
每对夫妻要么和新郎一排，要么和新娘一排所以容易想到用2-sat.
我们将丈夫编号为0~n-1,其对应的妻子编号+n（下面用i表示丈夫，i‘表示妻子）.
每对奸情则即是矛盾，则与其不矛盾的点连边，比如a与b矛盾，则连a->b‘,b->a‘,其意思是选a必须连b‘,不能选b。
这里用一个数组（kx[]）表示该点是否可选，或没被选。 初始值为0，表示未被选，1表示可选及已选，-1表示不可选。
每次选择了一个点后，就暴力搜接下来必须选择的点，然后把他们都选择，其伴侣都标记为不选择。如果不合法就换一种方式搜。
连边时要加一条新娘到新郎的边，因为新郎也可能有奸情，使其矛盾。
过程例如以下：a与新郎有奸情，矛盾，在开始建图时会使a->新娘，当如果爆搜选了a,则下面选新娘，标记新郎不可选，再通过建的这条边，发现爆搜a不可行，这样就避免了新郎与奸情坐一侧，这点很重要，而且我想了很久很久。。。。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5+10; struct node{ int u,v,next; }e[maxn]; int head[maxn],kx[maxn],n,m,top,cnt,st[maxn]; //kx数组判断是否可选，初始值为0, 1为可选且已选，-1为不可选。 int cp(int x){ return x<=n?x+n:x-n; }//返回cp编号 void add(int u,int v){e[cnt].u=u,e[cnt].v=v,e[cnt].next=head[u],head[u]=cnt++;} bool dfs(int x)//爆搜,判断编号x是否可选 { if(kx[x]==1) return true;//可选,且已被选。 if(kx[x]==-1) return false;//不可选 kx[x]=1,kx[cp(x)]=-1,st[++top]=x;//没被选，但是可被选，所以选入，其cp标为不可选。 for(int i=head[x];i!=-1;i=e[i].next) { if(!dfs(e[i].v))//判断相连的点是否可选，要选一起选。 return false; } return true; } void solve() { for(int i=1;i<=n;i++) { if(kx[i])//由0~i-1 连边判断已被选，不用进行下面操作 continue; top=0; if(!dfs(i))//kx[i]==0,没被选 ,且不可选 { while(top)//返回由i推到已选点，重新变成没选状态。 { kx[st[top]]=kx[cp(st[top])]=0; top--; } if(!dfs(i+n))//i不可选，且i+n也不可选，说明寻找不到答案。 { cout<<"bad luck"<<endl; return ; } } } for(int i=1;i<n;i++)//可以找到解 { if(kx[i]==-1)//当i不可选,则表示新娘不可见，放到新娘一边 cout<<i<<"h "; else//否则i+n不可选，所以i的妻子放在新娘一边 cout<<i<<"w "; } cout<<endl; } int main() { std::ios::sync_with_stdio(false); int x,y; char x1,y1; while(cin>>n>>m) { if(!n&&!m) break; memset(kx,0,sizeof(kx)); memset(head,-1,sizeof(head)); cnt=0; for(int i=0;i<m;i++) { cin>>x>>x1>>y>>y1; if(!x) x=n; if(!y) y=n; if(x1==‘h‘&&y1==‘h‘) add(x,y+n),add(y,x+n); else if(x1==‘h‘&&y1==‘w‘) add(x,y),add(y+n,x+n); else if(x1==‘w‘&&y1==‘h‘) add(x+n,y+n),add(y,x); else if(x1==‘w‘&&y1==‘w‘) add(x+n,y),add(y+n,x); } add(2*n,n);//加一条新娘到新郎的边，因为新郎可能有奸情 solve(); } return 0; }
原文：https://www.cnblogs.com/xiongtao/p/10611026.html