选书（深搜）

问题描述

n个同学分n本书，每个人都有自己喜欢的书（即a[i][j]==1），求出所有的分配方案

#include<iostream> 
#include<string>

using namespace std;

string name[25];//n个学生的名字 ，用于读入 
int c,n;//c记录可能的情况的个数，用于输出 
int flag[25],book[25],a[25][25];//flag记录第i本书是否被分，book记录第i个学生分到的书，a数组如题

void printx(){
    cout<<"answer"<<c<<":"<<endl;
    for (int i=1;i<n;i++){
        char ch=64+book[i]; 
        cout<<name[i]<<":"<<ch<<endl;
    }
}//输出第c种可能的情况 

void tried(int step){
    if (step==n+1){
        printx();
        return;
    }//所有人都分配过了就输出这种情况 
    for(int i=1;i<=n;i++){
        if(a[step][i]==1&&flag[i]==0){//第step个人对第i本书有兴趣，且第i本书没被分 
            flag[i]=1;
            book[step]=i;//记录
            tried(step+1);//递归
            flag[i]=0;
            book[step]=0;//回溯 
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
      flag[i]=0;//初始化flag数组，要养成这个习惯
    for(int i=1;i<=n;i++)
      cin>>name[i];//输入学生姓名 
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        cin>>a[i][j];
    tried(1);//从第一个学生开始分书
    return 0; 
}