2023-08-13 19:55:16
发布于：四川
1阅读
0回复
0点赞
来自洛谷。
[USACO19DEC] Livestock Lineup B
题目描述
每天，Farmer John 都要给他的 头奶牛挤奶。她们的名字分别是 Bessie，Buttercup，Belinda，Beatrice，Bella，Blue，Betsy，和 Sue。
不幸的是，这些奶牛相当难以伺候，她们要求 Farmer John 以一种符合 条限制的顺序给她们挤奶。每条限制的形式为“ 必须紧邻着 挤奶”，要求奶牛 在挤奶顺序中必须紧接在奶牛 之后，或者紧接在奶牛 之前。
请帮助 Farmer John 求出一种满足所有限制的奶牛挤奶顺序。保证这样的顺序是存在的。如果有多种顺序都满足要求，请输出字典序最小的一种。也就是说，第一头奶牛需要是所有可能排在任意合法奶牛顺序的第一位的奶牛中名字字典序最小的。在所有合法的以这头字典序最小的奶牛为首的奶牛顺序中，第二头奶牛需要是字典序最小的，以此类推。
输入格式
输入的第一行包含 。以下 行每行包含一句句子，以 " must be milked beside " 的格式描述了一条限制，其中 和 为 Farmer John 的某些奶牛的名字（上文列举了八个可能的名字）。
输出格式
请用 行输出一个奶牛的顺序，每行输出一头奶牛的名字，满足所有的限制。如果由多种顺序符合要求，输出字典序最小的奶牛顺序。
样例
样例输入 #1
3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice
样例输出 #1
Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup
题目描述源码：
# [USACO19DEC] Livestock Lineup B
## 题目描述
每天，Farmer John 都要给他的 $8$ 头奶牛挤奶。她们的名字分别是 Bessie，Buttercup，Belinda，Beatrice，Bella，Blue，Betsy，和 Sue。
不幸的是，这些奶牛相当难以伺候，她们要求 Farmer John 以一种符合 $N ( 1 \leq N \leq 7 )$ 条限制的顺序给她们挤奶。每条限制的形式为“$X$ 必须紧邻着 $Y$ 挤奶”，要求奶牛 $X$ 在挤奶顺序中必须紧接在奶牛 $Y$ 之后，或者紧接在奶牛 $Y$ 之前。
请帮助 Farmer John 求出一种满足所有限制的奶牛挤奶顺序。保证这样的顺序是存在的。如果有多种顺序都满足要求，请输出字典序最小的一种。也就是说，第一头奶牛需要是所有可能排在任意合法奶牛顺序的第一位的奶牛中名字字典序最小的。在所有合法的以这头字典序最小的奶牛为首的奶牛顺序中，第二头奶牛需要是字典序最小的，以此类推。
## 输入格式
输入的第一行包含 $N$。以下 $N$ 行每行包含一句句子，以 "$X$ must be milked beside $Y$" 的格式描述了一条限制，其中 $X$ 和 $Y$ 为 Farmer John 的某些奶牛的名字（上文列举了八个可能的名字）。
## 输出格式
请用 $8$ 行输出一个奶牛的顺序，每行输出一头奶牛的名字，满足所有的限制。如果由多种顺序符合要求，输出字典序最小的奶牛顺序。
后面的样例不再复制（复制到文本框会有问题）
有帮助，赞一个