易懂带注释题解

题意

每个学生有两本喜欢的书，能得到一本。要求计算出使得每个学生都能得到喜欢的书的分法数量。

解析

本题属于搜索中的子集枚举问题，需用到递归。递归层数为学生数量，每一层用于枚举每个学生的两种选书方法。在枚举前先判断该书是否还未已分给他人，否则就不能选择。如果能按当前递归路径走完最后一名学生，则计数变量自增一。

标程

#include<bits/stdc++.h>
using namespace std;
int x, ans;
bool flag[22];
int a[22], b[22];
void dfs(int k){
    if(k == x + 1){//成功枚举完所有同学
        ans++;
        return;//返回上一层
    }
    if(!flag[a[k]]){//判断第一本爱书是否没被选过
        flag[a[k]] = 1;
        dfs(k + 1);
        flag[a[k]] = 0;//回溯
    }
    if(!flag[b[k]]){//判断第二本爱书是否没被选过
        flag[b[k]] = 1;
        dfs(k + 1);
        flag[b[k]] = 0;
    }
    //如果两个书都已被选定，则返回上一层，试着改变上一名同学的选书
}
int main(){
    cin >> x;
    for(int i = 1; i <= x; i++){
        cin >> a[i] >> b[i];//记录每名同学喜欢的两本书
    }
    dfs(1);
    cout << ans;
    return 0;
}

本题解在核桃oj也有发布，均为本人所著