题解 P1657 【选书】

_YRH_ · 2016-08-19 09:46:59 · 题解

简单的递归题目~废话不说，直接看代码

#include<stdio.h>
#include<stdlib.h>
int i,j,k,m,n,x,y,sum,book[21];
bool flag[21],like[21][21];

int search(int z){//开始递归 
    int j;
    for(j=1;j<=n;j++)
        if(flag[j] && like[z][j]){//如果满足分书的条件即可开始 
            flag[j]=0;//吧被选中的书放入flag中，避免重复 
            book[z]=j;//保存第z个人选中的书j 
            if(z==n)//如果等于n，则每个人都分书了，累加sum 
                sum++;
            else 
                search(z+1);//否则继续递归 
            flag[j]=1;//回溯：把已经选中的书放回，产生其他的分书方案 
            book[z]=0;
        }
}

int main(){
    scanf("%d",&n);//读入 
    for(i=1;i<=n;i++){
        scanf("%d%d",&x,&y);//将每人喜爱的书存入like数组中 
        like[i][x]=1;
        like[i][y]=1;
        flag[i]=1;
    }
    search(1);//开始查找，从第一个书开始 
    printf("%d",sum);//输出sum即可~ 
    return 0;
}