如果你觉得这篇文章对你有帮助的话，请点点大拇指哦 题目描述 学校放寒假时，信息学奥赛辅导老师有1,2,3……x本书，要分给参加培训的x个人，每人只能选一本书，但是每人有两本喜欢的书。老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。
输入格式 第1行：一个数x
第2行第x+1行：每行两个数，表示ai喜欢的书的序号
输出格式 只有一个数：总方案数total。
输入输出样例 输入 5 1 3 4 5 2 5 1 4 3 5 输出 2
这是一道简单的深搜题目 我们可以将每个人夏欢的书分为一等和二等，并用一个结构体存储
struct like{ int one, two; //学生喜欢的书的编号 };这样我们可以在安排时，优先分配一等书，检查是否满足条件， 不满足条件的话在回溯到上一个学生的选书中选择二等书 样例： 如： 5 1 3 4 5 2 5 1 4 3 5 第一个同学选择一等书----1 此时选书数组中的数为{1，0，0，0，0} 第二位同学选择一等书----4 此时选书数组中的数为{1，4，0，0，0} 第三位同学选择一等书----2 此时选书数组中的数为{1，4，2，0，0} 到了第四位同学时，因为它所喜欢的书都被选完了，所以这种情况并不成立，我们就要回溯了，回溯到第三位同学选择二等书，发现并不能解决这种情况，我们在回溯到第二位同学， 第二位同学选择二等书----5 此时选书数组中的数为{1，5，0，0，0} 第三位同学选择一等书----2 此时选书数组中的数为{1，5，2，0，0} 第四位同学选择二等书----4 此时选书数组中的数为{1，5，2，4，0} 第五位同学选择一等书----3 此时选书数组中的数为{1，5，2，4，3} 这样我们就成功找到了第一种方式 当然后面还有一种方式我们就不详细解释了， 代码如下：
#include<bits/stdc++.h> using namespace std; int n, sum = 0; struct like{ int one, two; //学生喜欢的书的编号 }; void dfs(like a[], int i, int b[]) { if(n == 0) { //如果没有学生直接退出 return ; } if(i == n) { //深搜到第n次说明所有学生都找到了自己喜欢的书，满足条件，方案数加1 sum++; return ; } if(b[a[i].one] == 1 && b[a[i].two] == 1) return ; //该同学喜欢的书已经被选完了 if(b[a[i].one] == 0) { //选择一等书 b[a[i].one] = 1; dfs(a, i+1, b); b[a[i].one] = 0; //使一等书回溯到未被选择的状态 } if(b[a[i].two] == 0) { //选择二等书 b[a[i].two] = 1; dfs(a, i+1, b); b[a[i].two] = 0; //使二等书回溯到未被选择的状态 } } int main() { cin >> n; like a[n]; //学生喜欢的书的编号 int b[n+1]; //存储每一个学上选择的书的编号 memset(b, 0, sizeof(b)); for(int i = 0; i < n; i++) { cin >> a[i].one >> a[i].two; } dfs(a, 0, b); cout << sum <<endl; }