#OJ2286. 排队问题
排队问题
排队问题
Time Limit: 1 Sec Memory Limit: 128 MB
Description
qp学长要给n名ACM队员(编号为1-n)拍照,要求这n名队员站成一排。不过麻烦的是,有的队员之间出了点小矛盾,排队的时候不想站在相邻的位置,而有的队员之间关系非常铁,排队的时候想站在相邻的位置。qp学长应该如何安排,才能满足所有队员的要求呢?
Input
第一行为一个正整数T,代表样例组数。 每组样例的第一行为两个正整数n,m(n<=10,m<=n*(n-1)/2),代表队员人数以及限定条件个数。 接下来有m行,每行有三个整数f a b(f∈{0,1},1<=a,b<=n,a!=b),f为0代表a和b不想站在相邻的位置,f为1代表a和b想站在相邻的位置。 输入保证每组样例不存在任意ai,bi,aj,bj(i!=j),使得aiaj&&bibj或aibj&&ajbi。
Output
对于每组样例,第一行输出"Case #x: k",x为样例序号,k为满足条件的排队方法数。 接下来k行,每行输出一个满足条件的排队方法,按字典序递增的顺序输出。
Sample Input
3
3 2
1 1 2
1 2 3
3 2
0 1 2
0 2 3
3 2
0 1 2
1 2 3
Sample Output
Case #1: 2
1 2 3
3 2 1
Case #2: 0
Case #3: 2
1 3 2
2 3 1
HINT
仔细思考一下,对于能相邻和不能相邻的情况,分别应该怎么处理。 可以利用next_permutation函数(使用方法请自行查阅),也可以用dfs。