思路：将每对夫妻看成是对立状态，每个不正常关系都是一个矛盾，按2-SAT的方式建边。最后建一条新娘到新郎的边。具体看注释
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define Maxn 62 #define Maxm Maxn*Maxn using namespace std; int vi[Maxn],head[Maxn],dfn[Maxn],low[Maxn],e,n,lab,top,num,id[Maxn],Stack[Maxn],in[Maxn],Hash[Maxn],col[Maxn]; struct Edge{ int u,v,next; }edge[Maxm]; void init()//初始化 { memset(vi,0,sizeof(vi)); memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(id,0,sizeof(id)); memset(in,0,sizeof(in)); memset(col,0,sizeof(col)); e=lab=top=num=0; } void add(int u,int v)//加边 { edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++; } void Tarjan(int u)//找出强连通分支 { int i,j,v; dfn[u]=low[u]=++lab; Stack[top++]=u; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } if(vi[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { ++num; do{ i=Stack[--top]; vi[i]=0; id[i]=num; }while(i!=u); } } void buildGraphic()//缩点后重新建树，以便进行拓扑排序 { int ed=e,u,v; memset(head,-1,sizeof(head)); e=0; int i; for(i=0;i<ed;i++) { u=edge[i].u; v=edge[i].v; if(id[u]!=id[v]) { add(id[v],id[u]);//由于2-SAT问题中是找出度为0的点，这里我们建个反图，方便进行拓扑排序，变成找入度为0的点 in[id[u]]++; } } } void Topsort() { int i,j,u,v,temp; queue<int> q; int fron,rear; fron=rear=0; for(i=1;i<=num;i++) if(in[i]==0) q.push(i); while(!q.empty()) { temp=q.front(); q.pop(); if(!col[temp]) col[temp]=1,col[Hash[temp]]=2;//如果该连通分支未着色，那么给他着1，它的对立点就必须着不同的色 for(i=head[temp];i!=-1;i=edge[i].next) { v=edge[i].v; in[v]--; if(in[v]==0) q.push(v); } } } int solve() { int i,j; for(i=1;i<=2*n;i++) if(!dfn[i]) Tarjan(i); for(i=1;i<=n;i++) if(id[i]==id[i+n]) return 0;//有矛盾则结束 else Hash[id[i]]=id[i+n],Hash[id[i+n]]=id[i];//标记每个连通分支间的对立关系,即不能再同一侧 buildGraphic(); Topsort(); for(i=2;i<=n;i++) if(col[id[i]]==col[id[n+1]]) printf("%dh ",i-1);//输出和新娘同侧的人 else printf("%dw ",i-1); printf(" "); return 1; } int op(int x) { if(x<=n) return x+n; return x-n; } int main() { int m,i,j,a,b; char c1,c2; while(scanf("%d%d",&n,&m),n|m) { init(); for(i=0;i<m;i++) { scanf("%d%c%d%c",&a,&c1,&b,&c2);//husband点为1~N,wife点为N+1~2*N a++,b++; if(c1=='w') a+=n; if(c2=='w') b+=n; add(a,op(b)); add(b,op(a)); }//我们的目标是选择和新郎同一侧的，新郎固然在自己一侧。 add(n+1,1);//建一条由新娘到新郎的边，若选择了新娘，新郎也会被选，新郎和新娘成了同侧，便矛盾。即新娘不能和新郎同一侧 if(!solve()) printf("bad luck "); } return 0; }