题解 P1657 【选书】

_ljx_ · 2016-08-19 10:01:26 · 题解

C++（递归搜索）

#include<iostream>
using namespace std;// 废话不多说，进入正解
int sum=0,n;// 定义两个整型，一个储存次数，一个表示有几本书
int a[21];// 储存满足条件的书
bool b[100][100],g[100];// 一个记录喜欢的书，一个避免重复
int ll(int t)// 搜索
{
    int i,j,l;
    for(j=1;j<=n;j++)
    {
        if(b[t][j] && !g[j])// 满足条件的书
        {
            g[j]=1;// 避免重复
            a[t]=j;// 记录书（其实这是多余的）
            if(t==n) sum++;// 以完成了一种，sum累加
            else ll(t+1);// 否则，t+1，继续递归，向下走
            g[j]=0;    // 回溯：把选书的放回，产生其他的方案
            a[t]=0;  // 同上
        }
    }
}
int main()// 主函数：输入
{
    int i,l,j;
    cin>>n;// 输入几本书    
    for(i=1;i<=n;i++)
    {
        cin>>l>>j;
        b[i][l]=1;// 都是记录每人喜欢的书，将其赋值为1
        b[i][j]=1;
    }                
    ll(1);// 进入递归
    cout<<sum;// 哈哈，输出
    return 0;结束 ，功德圆满！！！
}