即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

分书相关疑难问题(搜索)

编程语言 Tsaryu 9℃ 0评论
D. 分书问题
Time Limit: 1000 ms   Memory Limit: 256 MB


Total Submission: 41   Submission Accepted: 16
Judge By Case
Description
已知有n本书(从1~n编号)和n个人(从1~n编号),每个人都有一个自己喜爱的书的列表,现在请你编写一个程序,设计一种分书方案,使得每个人都能获得一本书,且这本书一定要在他的喜爱列表中。



Input
输入数据共若干行,第一行为一个正整数n(n <= 20),从第2行到第n+1行,每行有n个0或1组成,第k行表示编号为k-1的人对这n本书的喜好列表,0表示不喜欢,1表示喜欢。



Output
输出数据仅一个整数,表示符合条件的分配方案的总数。



Sample Input
Original Transformed
5
00110
11001
01100
00010
01001



Sample Output
Original Transformed
1
题目分析:这个题目我是用dfs做的,dfs好久没有写了,还好,虽然耗时有点长,但是最后还是写出来了。主要是中间那个标志数组太菜了,本来可以用一个一维数组vis【i】表示第i本书是否已经被借走,我刚开始一直用二维数组,搞得好尴尬。不知道怎么恢复这个数组的标志位。后来一维数组之后才发现,是在利用过这个之后就直接恢复的。也是我dfs不够熟练吧。
#include 
#include 
#include 
#include 
#include 
using namespace std;
char a[25][25];
bool vis[25];
int ans,flag;
int n;
int cou[25];
void dfs(int m,int k){
 //表明第k本书已经被分配 
 if(m>n || m<1 )
   return ;
   for(int i=1;i<=n;i++){
    if(a[m+1][i] == '1' && vis[i] == 0 ){
   vis[i] = 1;
   if(m+1 == n){
     ans++;
    // return;
   }
   //如果到达最终边,直接ans++; 
   else dfs(m+1,i);//否则继续搜索 
         vis[i] = 0;
  }
   }
}
int main(){
 cin>>n;
 memset(a,-1,sizeof(a));
    char sh[25];
 for(int i=1;i<=n;i++){
   cin>>sh;
   for(int j=0;j





转载请注明:CodingBlog » 分书相关疑难问题(搜索)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情