题目来源:
题目大意:ACM城的美食俱乐部有16位成员。他们连续了当地的法国餐厅Chatrau Java来安排连续5天的晚餐。晚餐时他们每4人1桌,共4桌。他们希望5次晚餐中,每个成员都跟其他的所有成员恰好同桌进餐一次。餐厅主人Maitre D'先生被安排来完成俱乐部成员的座位安排和调度。Maitre D'做了前三天的座位安排,保证了每个成员没有与其他的任一个成员同桌过两次,但不幸的是Maitre D'先生在第四天不见了,只留下了前三天座位安排的记录。现在要请你帮忙看能够合理地安排接下来两天中各位成员的座位,使得5天里每个成员与其他各成员恰好同桌一次。下面是Maitre D'先生留下的记录的样例:
ABCD EFGH IJKL MNOP
AEIM BFJN CGKO DHLP AFKP BGLM CHIN DEJO俱乐部成员编号为A,B,C,...,P。
每一行代表一天晚餐的座位安排,连在一起的4个编号表示该4个人同桌。
输入:每个数据集含3行,每行4个块,每个块4个字母。所有字母都为大写。块之间用空格隔开。数据集之间用空行隔开。
输出:若能找到一个可行的后两天的座位安排,则按顺序输出整个5天的安排,若不可能完成安排,则输出"It is not possible to complete this schedule." 数据集之间用空行隔开。
Sample Input
ABCD EFGH IJKL MNOPAEIM BFJN CGKO DHLPAFKP BGLM CHIN DEJO
Sample Output
It is not possible to complete this schedule.
解题思路:
总人数16人,每个人要求与其他每个人都恰好同桌一次。
那么在前三天之后,每个人都还有6个人没有同桌过。
假设与A没有同桌过的6人组成集合S(A),假定B属于S(A), 未与B同桌过的人组成集合S(B). A与B必须要同桌一次,而他们同桌时还需要再找两个与A和B都没有同桌过的人来凑数。
那么如果S(A)∩S(B)少于2人,则无法凑出一桌,说明无法达到目标。
如果S(A)∩S(B)大于2人,那么假定选出两人凑成这一桌,那么至少还剩下一人需要在另一天里即与A同桌也与B同桌才可能满足与每个人都同桌过,而A和B已经同桌过了,所以也无法达到目标。
所以只有S(A)与S(B)的交集恰好为2人时可能达成目标。由此规则,一直凑桌就可以了。
代码如下,最开始用了两个goto语句写的,后来改为下面不含goto的版本,可是代码长了好多(=。=).
1 // 2 // POJ1058 The Gourmet Club 3 // Memory: 180K Time: 0MS 4 // Language: C++ Result: Accepted 5 // 6 7 #include8 #include 9 #include 10 11 using namespace std; 12 13 int graph[16][16]; //graph[i][j]为0表示该两人未同桌过,为1表示已同桌过 14 char schedule[5][4][4]; //schedule[i][j][k]表示第 i + 1 天第 j + 1 桌的第 k + 1 个人 15 16 int main(void) { 17 while (true) { 18 memset(graph, 0, sizeof(graph)); 19 20 //读入前三天的座位安排 21 for (int i = 0; i < 3; ++i) { 22 for (int j = 0; j < 4; ++j) { 23 for (int k = 0; k < 4; ++k) { 24 if (!(cin >> schedule[i][j][k])) { 25 return 0; 26 } 27 } 28 //用graph记录同桌关系 29 for (int p = 0; p < 4; ++p) { 30 for (int q = 1; q < 4; ++q) { 31 graph[schedule[i][j][p] - 'A'][schedule[i][j][q] - 'A'] = 1; 32 graph[schedule[i][j][q] - 'A'][schedule[i][j][p] - 'A'] = 1; 33 } 34 } 35 } 36 } 37 38 bool flag = true; 39 for (int i = 3; flag && i < 5; ++i) { 40 //第 i + 1 天 41 bool settled[16]; //记录已安排座位的人 42 for (int t = 0; t < 16; ++t) { 43 settled[t] = false; 44 } 45 //凑前三桌的人 46 for (int j = 0; flag && j < 3; ++j) { 47 int a = -1, b = -1, c = -1, d = -1; 48 set sa, sb, si; 49 set ::iterator itr; 50 itr = si.begin(); 51 for (a = j; flag && a < 16; ++a) { 52 if (settled[a] == false) { 53 //找出一个该日未落座的人a 54 for (int t = a + 1; flag && t < 16; ++t) { 55 //未与a同座过的人组成sa 56 if (!settled[t] && !graph[a][t]) { 57 sa.insert(t); 58 } 59 } 60 if (sa.size() >= 3) { 61 b = *(sa.begin()); 62 //未与b同座过的组成sb 63 for (int t = a; t < 16; ++t) { 64 if (!settled[t] && !graph[b][t]) { 65 sb.insert(t); 66 } 67 } 68 if (sb.size() < 3) { 69 flag = false; 70 } 71 } else { 72 flag = false; 73 } 74 if (flag) { 75 //求交集并判断交集人数 76 set_intersection(sa.begin(), sa.end(), sb.begin(), sb.end(), inserter(si, itr)); 77 int k; 78 if (si.size() == 2) { 79 for (k = 2, itr = si.begin(); itr != si.end(); itr++, ++k) { 80 schedule[i][j][k] = (*itr) + 'A'; 81 } 82 schedule[i][j][0] = a + 'A'; 83 schedule[i][j][1] = b + 'A'; 84 c = schedule[i][j][2] - 'A'; 85 d = schedule[i][j][3] - 'A'; 86 graph[a][b] = graph[b][a] = graph[a][c] = graph[c][a] = graph[a][d] 87 = graph[d][a] = graph[b][c] = graph[c][b] = graph[c][d] 88 = graph[d][c] = 1; 89 settled[a] = settled[b] = settled[c] = settled[d] = true; 90 } else { 91 flag = false; 92 } 93 } 94 break; 95 } 96 } 97 } 98 //剩下的为第四桌 99 for (int t = 0, p = 0; flag && t < 16; ++t) {100 if (!settled[t]) {101 schedule[i][3][p++] = t + 'A';102 }103 }104 }105 106 //输出107 if (flag) {108 for (int i = 0; i < 5; ++i) {109 for (int j = 0; j < 4; ++j) {110 for (int k = 0; k < 4; ++k) {111 cout << schedule[i][j][k];112 }113 if (j != 3) {114 cout << " ";115 }116 }117 cout << endl;118 }119 } else {120 cout << "It is not possible to complete this schedule." << endl;121 }122 }123 return 0;124 }