题解 P1657 【选书】

· · 题解

这道题属于暴力搜索；变化在于一个人喜爱两本书；

根据数据范围（20）用深搜即可不会广搜

不考虑x==0的情况最后一个点过不了。然而无法理解分发0本书给0个人

以下代码忽略其中多余的大括号，本人强迫症晚期

 #include <iostream>
 using namespace std;
 const int maxn=21;//考虑数据规模 
 int a[maxn][2],t=0,vis[maxn],x;
 // 数组a存贮每个学生喜爱的书；a[i][j]表示学生i喜爱的第j本书；vis数组标记是否搜索过； 
 void dfs(int xx){
    if(xx==x+1)t++;//如果搜索完成，增加方案数； 
    else{
       for(int i=1;i<=x;i++){ //选择每一本书 
        for(int j=0;j<=1;j++){ 
            if((!vis[i])&&(a[xx][j]==i)){//如果这书i没有被选走，并且同学x喜爱这本书 
                vis[i]=1;//标记书i； 
                dfs(xx+1);//进行下一位同学的搜索 
                vis[i]=0;//释放书i，便于继续搜索； 
            }
        }
       }
    }
 }
 int  main(){
    cin>>x; 
    if(x){//有x==0这种毒瘤的情况；（无法理解将0本书分发给0位同学23333）
    //当x!=0时使用常规的搜索思路； 
    for(int i=1;i<=x;i++){
        cin>>a[i][0]>>a[i][1];//读入每位同学喜爱的书的编号； 
     }
     dfs(1);
     cout<<t;//输出结果 
    }
     else cout<<0;//如果人数为零则无法分发
return 0; 
 }

搜索题目本身思考价值较低，然而考验耐心和细节；

首个题解；如果肯定有错误敬请指出，感激不尽