洛谷p1657：选书

题目链接：https://www.luogu.com.cn/problem/P1657#submit
学校放寒假时，信息学奥赛辅导老师有1,2,3……x本书，要分给参加培训的x个人，每人只能选一本书，但是每人有两本喜欢的书。老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。
方法：可以使用深搜来实现，直接贴代码，在代码里解释

#include
using namespace std;
struct sh{    //用结构体来存书号int sh1;int sh2;
}a[25];
long long sum=0;
int v[25];
void df(int bb,int cc)  //进行深搜
{bb++;if(v[a[bb].sh1]==0){   //说明学号为bb的人喜欢的第一本书还在if(bb==cc-1) {sum++;return;  //说明有这么一个序列}v[a[bb].sh1]=1;  //因为该书已经被选df(bb,cc); //继续往下搜索v[a[bb].sh1]=0;  //重点，一定要有，不然会出错}if(v[a[bb].sh2]==0)    //说明学号为bb的人喜欢的第二本书还在{if(bb==cc-1) {sum++;return;}v[a[bb].sh2]=1;df(bb,cc);v[a[bb].sh2]=0;}return;
}
int main()
{int x;cin>>x;for(int i=0;i<x;i++){cin>>a[i].sh1>>a[i].sh2;}memset(v,0,sizeof(v)); v[a[0].sh1]=1;df(0,x);memset(v,0,sizeof(v));  //清数组v[a[0].sh2]=1;df(0,x);cout<<sum;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！