Time Limit: 1000MS | Memory Limit: 65536K | |||
Total Submissions: 7920 | Accepted: 2394 | Special Judge |
Description
Up to thirty couples will attend a wedding feast, at which they will be seated on either side of a long table. The bride and groom sit at one end, opposite each other, and the bride wears an elaborate headdress that keeps her from seeing people on the same side as her. It is considered bad luck to have a husband and wife seated on the same side of the table. Additionally, there are several pairs of people conducting adulterous relationships (both different-sex and same-sex relationships are possible), and it is bad luck for the bride to see both members of such a pair. Your job is to arrange people at the table so as to avoid any bad luck.
Input
The input consists of a number of test cases, followed by a line containing 0 0. Each test case gives n, the number of couples, followed by the number of adulterous pairs, followed by the pairs, in the form "4h 2w" (husband from couple 4, wife from couple 2), or "10w 4w", or "3h 1h". Couples are numbered from 0 to n - 1 with the bride and groom being 0w and 0h.
Output
For each case, output a single line containing a list of the people that should be seated on the same side as the bride. If there are several solutions, any one will do. If there is no solution, output a line containing "bad luck".
Sample Input
10 6 3h 7h 5w 3w 7h 6w 8w 3w 7h 3w 2w 5h 0 0
Sample Output
1h 2h 3w 4h 5h 6h 7h 8h 9h
题意:
给出 N(<= 30)对夫妇 和 M 对通奸关系。现在这些人要和一堆新婚夫妇在饭桌前吃饭,饭桌面对着共有两边。夫妻必须面对面做,新娘能望见对面的所有人,新娘不能同时看见一对通奸关系的人。现要安排座位,是否能按要求分配座位。
思路:
2 - sat。新娘新郎的位置要判矛盾,故要增加两条边。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <vector> #include <stack> using namespace std; const int NMAX = 65 * 2; int n, m; vector<int> G[NMAX]; int res[NMAX]; int pre[NMAX], low[NMAX], cmp[NMAX]; int dfs_clock, scc_cnt; stack<int> s; void dfs(int u) { pre[u] = low[u] = ++dfs_clock; s.push(u); for (int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if (!pre[v]) { dfs(v); low[u] = min(low[u], low[v]); } else if (!cmp[v]) { low[u] = min(low[u], pre[v]); } } if (pre[u] == low[u]) { ++scc_cnt; for ( ;;) { int x = s.top(); s.pop(); cmp[x] = scc_cnt; if (x == u) break; } } } void scc() { dfs_clock = scc_cnt = 0; memset(pre, 0, sizeof(pre)); memset(cmp, 0, sizeof(cmp)); for (int i = 0; i < 2 * n; ++i) { if (!pre[i]) dfs(i); } } int main() { while (~scanf("%d%d", &n, &m) && (n + m)) { n *= 2; for (int i = 0; i < 2 * n; ++i) G[i].clear(); for (int i = 0; i < n; i += 2) { G[i].push_back(i + 1 + n); G[i + n].push_back(i + 1); G[i + 1].push_back(i + n); G[i + 1 + n].push_back(i); } G[n + 0].push_back(0); //固定新娘只能在一边坐 G[1].push_back(1 + n); //固定新郎只能在对面坐 while (m--) { int A, B; char sex; scanf("%d%c", &A, &sex); A = A * 2 + (sex == 'h'); scanf("%d%c", &B, &sex); B = B * 2 + (sex == 'h'); G[A + n].push_back(B); G[B + n].push_back(A); } scc(); int temp = 0; for (int i = 0; i < n; ++i) { if (cmp[i] == cmp[i + n]) { printf("bad luck\n"); temp = 1; break; } } if (!temp) { int ans = 0; for (int i = 2; i <= n; ++i) if (cmp[i] < cmp[i + n]) res[ans++] = i; for (int i = 0; i < ans; ++i) { printf("%d", res[i] / 2); res[i] % 2 ? printf("h") : printf("w"); i == ans - 1 ? printf("\n") : printf(" "); } } } return 0; }
相关推荐
这是AE模板,名为:7701 Wedding Intro-玫瑰花瓣婚礼相册片头
wedding-marta-daniele-源码.rar
wedding-fair-pure-html-css-js
Wedding-Dress-Boxes:源代码
婚礼照相应用程序 相依性 版本 苹果系统 卡塔琳娜10.15.7 节点 v15.4.0 npm 7.0.15 Nuxt ...git clone https://github.com/taiga-tech/wedding-photo-nuxt/ cd wedding-photo-nuxt npm install npm run dev 参考
Wedding-invitation婚礼邀请函微信小程序,前端+后端+数据库 小程序前端是fork的 现在已经迁移到云开发,不需要域名和服务器。前提申请一个小程序账号入门clone本项目,并通过微信开发工具导入,导入时填入你的appid...
Wedding-RSVP-网站
一个Web应用程序,用于管理来宾列表(带有联系信息),rsvps,到达时间,角色,菜单,组,礼物和感谢。 婚礼策划的理想选择。
raechel-wedding-site
my-wedding-website
小鹰正在为自己的婚礼做准备,她所有的朋友都被邀请参加婚礼。帮助小鹰为她的梦想婚礼做准备,图片 小鹰正在为自己的婚礼做准备,并邀请所有朋友参加婚礼。帮助小鹰为自己的梦想婚礼做准备,挑选最好的婚纱,漂亮的...
语言:English 关于喀拉拉邦婚礼趋势的所有信息。 喀拉拉邦婚礼趋势:trade_mark:是一本完整的婚礼指南,提供了喀拉拉邦婚姻的最新趋势。 它涵盖了婚礼摄影,摄影,珠宝,服饰,食品和婚礼的所有其他主要必需品。...
Sparsh-Aalisha-Wedding-RSVP
michelle-andrew-wedding-website
最好的婚礼摄影师,你的钱,期间。 Pixelicious是一位来自加拿大蒙特利尔的婚礼摄影师,它迎合那些希望在婚礼当天获得不妥协体验的最独特,最特权的新娘。 通过提供优质的图像,出色的客户服务和难忘的体验,...
婚礼桌规划师网站 您可以尝试 。 这是一个小型网络应用程序,可用于安排客人。 您可以设置“已知”,“被爱... rhc app-create weddingtablesplanner diy-0.1 --from-code git://github.com/juanignaciosl/wedding-tab
WEDDING
紫色漂亮的恋爱结婚wedding网站模板_紫色 漂亮 恋爱 结婚 交友 婚礼 幻灯 菜单 wedding 可爱 html5 整站.rar