题意:
给n对夫妻安排座位,每对夫妻相对而坐,给出m对特殊关系,有特殊关系的人不能一起坐在新娘对面。
分析:
2-sat+输出解。
代码:
#include <iostream>
#include <stack>
#include <vector>
#include <queue>
using namespace std;
const int maxN=1024;
const int maxM=42000;
int e,e1,n,m,t,ecnt;
int head[maxN],head1[maxN],ins[maxN],low[maxN],dfn[maxN];
int sol[maxN],belong[maxN],d[maxN],ans[maxN];
int cf[maxN],color[maxN],vis[maxN];stack<int> s;
queue<int> Q;struct Edge
{int u,v,next;
}edge[maxM],edge1[maxM];void addegde(int u,int v)
{edge[e].u=u;edge[e].v=v;edge[e].next=head[u];head[u]=e++;
}void addegde1(int u,int v)
{edge1[e1].u=u;edge1[e1].v=v;edge1[e1].next=head1[u];head1[u]=e1++;
}
void dfs(int x)
{low[x]=dfn[x]=++t; s.push(x);ins[x]=1;for(int i=head[x];i!=-1;i=edge[i].next){int v=edge[i].v;if(!dfn[v]){dfs(v);low[x]=min(low[x],low[v]);}else if(ins[v]==1)low[x]=min(low[x],dfn[v]);} if(dfn[x]==low[x]){++ecnt; int k;do{k=s.top();s.pop();ins[k]=0;belong[k]=ecnt;}while(k!=x);}
}void build()
{int i;e1=0;memset(head1,-1,sizeof(head1));memset(d,0,sizeof(d));memset(color,0,sizeof(color));for(i=0;i<e;++i)if(belong[edge[i].u]!=belong[edge[i].v]){addegde1(belong[edge[i].v],belong[edge[i].u]);++d[belong[edge[i].u]];}while(!Q.empty()) Q.pop();memset(vis,0,sizeof(vis));for(i=1;i<=ecnt;++i)if(d[i]==0)Q.push(i);while(!Q.empty()){int u=Q.front();vis[u]=1;Q.pop();if(color[u]==0){color[u]=1;color[cf[u]]=-1;}for(int i=head1[u];i!=-1;i=edge1[i].next){int v=edge1[i].v;--d[v];if(d[v]==0&&vis[v]==0)Q.push(v);}} memset(ans,0,sizeof(ans)); for(i=0;i<n;++i){if(color[belong[2*i+1]]==1)ans[i]=1;}}int two_sat()
{memset(ins,0,sizeof(ins)); memset(dfn,0,sizeof(dfn)); while(!s.empty()) s.pop();int i;t=0,ecnt=0;for(i=0;i<2*n;++i)if(!dfn[i])dfs(i);for(i=0;i<n;++i)if(belong[2*i]==belong[2*i+1])return 0;else{cf[belong[2*i]]=belong[2*i+1];cf[belong[2*i+1]]=belong[2*i]; } build();return 1;
}int main()
{int i;while(scanf("%d%d",&n,&m)==2){if(n==0&&m==0) break;char c1,c2;int d1,d2,x,y;e=0;memset(head,-1,sizeof(head));for(i=0;i<m;++i){scanf("%d%c%d%c",&d1,&c1,&d2,&c2); if(c1=='h')x=2*d1+1;elsex=2*d1;if(c2=='h')y=2*d2+1;elsey=2*d2;addegde(x,y^1);addegde(y,x^1); }addegde(0,1);if(two_sat()==0)printf("bad luck\n");else{for(i=1;i<n;++i){if(ans[i]==1)printf("%dw ",i);elseprintf("%dh ",i);}printf("\n");}} return 0;
}
上面的算法用tarjan算法求强连通分量,求完后还要求DAG,比较繁琐,相比之下,下面的做法用Kosaraju算法求强联通分量,因为Kosaraju的结果是拓扑有序的(很有用的性质),所以可以省略求DAG的步骤,代码量减少了50%,清晰简洁不少:
#include <iostream>
#include <vector>
using namespace std;
const int maxN=200;
vector<int> g[maxN],ng[maxN];
int n,m,cnt,scc,ans[maxN],vis[maxN],dfn[maxN],cf[maxN],color[maxN];void addegde(int u,int v)
{g[u].push_back(v);ng[v].push_back(u);
}void dfs(int k)
{vis[k]=1;for(int i=g[k].size()-1;i>=0;--i)if(!vis[g[k][i]])dfs(g[k][i]);dfn[++cnt]=k;
}void ndfs(int k)
{vis[k]=scc;for(int i=ng[k].size()-1;i>=0;--i)if(!vis[ng[k][i]])ndfs(ng[k][i]);
}
void kosaraju()
{memset(vis,0,sizeof(vis));cnt=0;for(int i=0;i<2*n;++i)if(!vis[i])dfs(i); memset(vis,0,sizeof(vis));scc=0;for(int i=2*n;i>=1;--i)if(!vis[dfn[i]]){++scc;ndfs(dfn[i]);}
}int two_sat()
{int i;kosaraju();for(i=0;i<n;++i)if(vis[2*i]==vis[2*i+1])return 0; else{cf[vis[2*i]]=vis[2*i+1];cf[vis[2*i+1]]=vis[2*i]; }memset(color,0,sizeof(color));for(i=scc;i>=1;--i)if(color[i]==0){color[i]=1;color[cf[i]]=-1;}memset(ans,0,sizeof(ans));for(i=0;i<n;++i)if(color[vis[2*i+1]]==1)ans[i]=1; return 1;
}int main()
{int i;while(scanf("%d%d",&n,&m)==2){if(n==0&&m==0) break;char c1,c2;int d1,d2,x,y;for(i=0;i<2*n;++i) g[i].clear(),ng[i].clear(); for(i=0;i<m;++i){scanf("%d%c%d%c",&d1,&c1,&d2,&c2); if(c1=='h')x=2*d1+1;elsex=2*d1;if(c2=='h')y=2*d2+1;elsey=2*d2;addegde(x,y^1);addegde(y,x^1); }addegde(0,1);if(two_sat()==0)printf("bad luck\n");else{for(i=1;i<n;++i){if(ans[i]==1)printf("%dw ",i);elseprintf("%dh ",i);}printf("\n");}} return 0;
}