AOJ.863分配书籍问题（深度优先搜索算法）

题意分析

现有n个人&＃xff0c;n种书&＃xff0c;给出每人对n种书的喜欢列表&＃xff0c;求有多少种方案满足以下条件&＃xff1a;

1.每个人都分得自己喜欢的书&＃xff1b;
2.每个人分得书的种类各不相同&＃xff0c;即所有种类的书均得到分配

1.采用生成测试法
生成过程
对于每个人来说&＃xff0c;枚举每本书的状态&＃xff08;0/1&＃xff09;&＃xff0c;有2^20&＃xff1b;
最多有20个人 &＃xff0c;则有20*2^20 &＃61; 10*2^21 ≈ 10^3 * 10 ^3 * 10 &＃61; 10^ 7
考虑上测试的时间&＃xff0c;TLE。

2.优化
充分利用题目中给的信息&＃xff0c;即每个人对不同书的喜爱我们是已知的。对于每个人来说&＃xff0c;我们不需要枚举全部书籍的状态&＃xff0c;只需要枚举他喜爱的每本书的状态&＃xff0c;即从他喜欢的书籍中选一本给他&＃xff0c;然后再看下一个人&＃xff0c;再从这个人喜爱的书籍中选一本给他…… 直到所有人都分得书籍。然后再检查是否所有的书籍都得到分配&＃xff0c;若是&＃xff0c;ans&＃43;&＃43;&＃xff0c;否则继续枚举下一种分配情况。

代码总览

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define nmax 25
#define MEM(x) memset(x,0,sizeof(x))
using namespace std;
vector<int> v[nmax];
bool bookvisit[nmax];
bool peoplevisit[nmax];
int ans &＃61; 0,n;
bool check()
{for(int i &＃61; 0; iif(!bookvisit[i] || !peoplevisit[i])return false;}return true;
}
void dfs(int peo)
{if(peo &＃61;&＃61; n){if(check()) ans&＃43;&＃43;;return;}peoplevisit[peo] &＃61; true;for(int i &＃61; 0; iif(!bookvisit[v[peo][i]]){bookvisit[v[peo][i]] &＃61; true;dfs(peo&＃43;1);bookvisit[v[peo][i]] &＃61; false;}}
}
void init()
{MEM(peoplevisit);MEM(bookvisit);ans &＃61; 0;
}
int main()
{//freopen("in.txt","r",stdin);char str[nmax];while(scanf("%d",&n)!&＃61; EOF){init();for(int i &＃61;0 ;iscanf("%s",str);for(int j &＃61; 0;j<strlen(str);&＃43;&＃43;j)if(str[j] &＃61;&＃61; &＃39;1&＃39;) v[i].push_back(j);}dfs(0);printf("%d\n",ans);}return 0;
}