G. Livestock Lineup

GDUT 2020寒假训练 专题一 H

原题链接

• G. Livestock Lineup

题目

Every day, Farmer John milks his 8 dairy cows, named Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, and Sue. The cows are rather picky, unfortunately, and require that Farmer John milks them in an order that respects N constraints (1≤N≤7). Each constraint is of the form “X must be milked beside Y”, stipulating that cow X must appear in the milking order either directly after cow Y or directly before cow Y.

Please help Farmer John determine an ordering of his cows that satisfies all of these required constraints. It is guaranteed that an ordering is always possible. If several orderings work, then please output the one that is alphabetically first. That is, the first cow should have the alphabetically lowest name of all possible cows that could appear first in any valid ordering. Among all orderings starting with this same alphabetically-first cow, the second cow should be alphabetically lowest among all possible valid orderings, and so on.

Input
The first line of input contains N. The next N lines each contain a sentence describing a constraint in the form “X must be milked beside Y”, where X and Y are names of some of Farmer John’s cows (the eight possible names are listed above).

Output
Please output, using 8 lines, an ordering of cows, one cow per line, satisfying all constraints. If multiple orderings work, output the one that is alphabetically earliest.

样例

input：
3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice
output：
Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

题目大意

有八头牛排序，下面给出N个要求，每个要求中都提出了x想和y排在一起，请输出所有合法的排序方案中名字的字典序最小的

思路

枚举
用next_permutation枚举出各种可能的方案，然后对每一个方案进行检查，检查的过程就是循环判断N个要求是否都满足。
在枚举之前还进行了一下预处理，首先先把这八个名字扔到set里面得到字典序的排列，然后依据字典序从1~8建立string to int（用于输入）和int to string（用于输出） 的双映射，在枚举的时候操作的数组是{1,2,3,4,5,6,7,8}然后输出的时候用映射给映射回来就行。

数据量很小，直接暴力枚举不考虑后果，干就完了 奥利给。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
using namespace std;
map<string ,int> si;
map<int,string> is;
set<string> str;
int num[8]={1,2,3,4,5,6,7,8};
int order[10][2];
int main()
{
/*	str.insert("Bessie");
	str.insert("Buttercup");
	str.insert("Beatrice");
	str.insert("Belinda");
	str.insert("Bella");
	str.insert("Blue");
	str.insert("Betsy");
	str.insert("Sue");
	for(set<string>::iterator i=str.begin();i!=str.end();i++)
	{
		cout<<*i<<" "<<endl;
	}*/
	si["Beatrice"]=1;	is[1]="Beatrice";
	si["Belinda"]=2;	is[2]="Belinda";
	si["Bella"]=3;		is[3]="Bella";
	si["Bessie"]=4;		is[4]="Bessie";
	si["Betsy"]=5;		is[5]="Betsy";
	si["Blue"]=6;		is[6]="Blue";
	si["Buttercup"]=7;	is[7]="Buttercup";
	si["Sue"]=8;		is[8]="Sue";
	int m;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		string str;
		cin>>str;
		order[i][0]=si[str];
		cin>>str>>str>>str>>str>>str;
		order[i][1]=si[str];
	}
	while(next_permutation(num,num+8))
	{
		bool flag=true;
		for(int i=1;i<=m;i++)
		{
			bool f=false;
			for(int j=1;j<=6;j++)
			{
				if(num[j]==order[i][0]&&(num[j-1]==order[i][1]||num[j+1]==order[i][1]))
				{
					//flag++;
					f=true;
					break;
				}
				if(num[j]==order[i][1]&&(num[j-1]==order[i][0]||num[j+1]==order[i][0]))
				{
					//flag++;
					f=true;
					break;
				}
			}
			if(f==false)
			{
				flag=false;
				break;
			}
		}
		if(flag==true)
		{
			for(int i=0;i<=7;i++)
			{
				cout<<is[num[i]]<<endl;
			}
			return 0;
		}
	}
	return 0;
}