题目链接:Click here~~
题意:
30对夫妇去参加一场婚礼,有一条长桌子,丈夫和妻子不能坐在一侧。然后,有些冲突关系,具有那些冲突关系的人不能同时坐在新娘的对面。
输出坐在新娘这侧的人的编号。
解题思路:
搞了3天多的题。搞不出来的时候想死。刚才发现一个 v 打成了i ,呵呵***。
怎么输出方案呢?
先对缩点后的图重新建图,这里的图要逆向建立。
因为原图 u->v 表示,要选 u 就一定选 v,即选 u 是选 v 的充分条件,但答案不一定选 u 。所以那样的话,实现还要dfs,复杂度太高。
方法是逆向建图。然后拓扑排序。将每次得到的点染成红色,对立的点染成蓝色,最后染成红色的点就是方案中的点。
另外此题虽然要的是坐在新娘这侧的编号,但我们求方案时还是要求坐在新娘对面的方案,因为冲突的关系来自对面。
可以添加一条新娘到新郎的边,防止选新娘到对面。
paint() 函数貌似是没用的。
#include <queue> #include <stack> #include <vector> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1e2+3; const int M = 2e4+5; struct Vertex { int head; }V[N],VV[N]; struct Edge { int v,next; }E[M],EE[M]; int top,topp,scc,index,dfn[N],low[N],ind[N],belong[N],opp[N]; bool in[N],vis[N],color[N]; stack<int> S; void init() { top = topp = 0; memset(V,-1,sizeof(V)); memset(VV,-1,sizeof(VV)); } void add_edge(int u,int v) { E[top].v = v; E[top].next = V[u].head; V[u].head = top++; } void add_edge2(int u,int v) { EE[topp].v = v; EE[topp].next = VV[u].head; VV[u].head = topp++; } void tarjan(int u) { dfn[u] = low[u] = ++index; S.push(u); in[u] = true; for(int i=V[u].head;~i;i=E[i].next) { int v = E[i].v; if(!dfn[v]) { tarjan(v); low[u] = min(low[u],low[v]); } else if(in[v]) low[u] = min(low[u],dfn[v]); } if(dfn[u] == low[u]) { int v; do { v = S.top(); S.pop(); in[v] = false; belong[v] = scc; }while(u != v); scc++; } } void get_scc(int n) { scc = index = 0; memset(dfn,0,sizeof(dfn)); memset(in,false,sizeof(in)); for(int i=0;i<n;i++) if(!dfn[i]) tarjan(i); } bool conflict(int n) { for(int i=0;i<n;i++) if(belong[i<<1] == belong[i<<1|1]) return true; else { opp[ belong[i<<1] ] = belong[i<<1|1]; opp[ belong[i<<1|1] ] = belong[i<<1]; } return false; } void rebuild(int n) { memset(ind,0,sizeof(ind)); for(int u=0;u<n;u++) { for(int j=V[u].head;~j;j=E[j].next) { int v = E[j].v; if(belong[u] == belong[v]) continue; ind[belong[u]]++; //ni'tu add_edge2(belong[v],belong[u]); } } } void paint(int u) { for(int i=VV[u].head;~i;i=EE[i].next) { int v = EE[i].v; if(!vis[v]) { vis[v] = true; paint(v); } } } void topSort() { memset(vis,false,sizeof(vis)); memset(color,false,sizeof(color)); queue<int> q; for(int i=0;i<scc;i++) if(!ind[i]) q.push(i); while(!q.empty()) { int u = q.front(); q.pop(); if(vis[u]) continue; vis[u] = true; color[u] = true; int v = opp[u]; if(!vis[v]) { vis[v] = true; paint(v); } for(int i=VV[u].head;~i;i=EE[i].next) { int v = EE[i].v; if(--ind[v] == 0) q.push(v); } } } int main() { //freopen("in.ads","r",stdin); int n,m; while(~scanf("%d%d",&n,&m),n||m) { init(); while(m--) { int u,v; char c1,c2; scanf("%d%c %d%c",&u,&c1,&v,&c2); u = c1=='w' ? u<<1 : u<<1|1; v = c2=='w' ? v<<1 : v<<1|1; add_edge(u,v^1); add_edge(v,u^1); } add_edge(0,1); get_scc(n<<1); if(conflict(n)) puts("bad luck"); else { rebuild(n<<1); topSort(); for(int i=1;i<n;i++) printf("%d%c%c",i,color[ belong[i<<1] ] ? 'h' : 'w',i==n-1?'\n':' '); } } return 0; }