AOJ 863.分书问题|OhYee 博客

这是一篇最后编辑于 8 年前的文章，其内容可能与目前实际情况差异较大，请注意甄别

题目

{% fold 点击显/隐题目 %}

已知有n本书（从1～n编号）和n个人（从1～n编号），每个人都有一个自己喜爱的书的列表，现在请你编写一个程序，设计一种分书方案，使得每个人都能获得一本书，且这本书一定要在他的喜爱列表中。

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

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

5 00110 11001 01100 00010 01001

{% endfold %}

题解

暴力DFS即可,最差情况 20*20 个 1 是过不了的
问题为二分图匹配方案数计数,为NP问题,只能暴力解决
因此可以不用考虑极端情况,尽量优化即可

发现有人分不到书直接返回.

代码

{% fold 点击显/隐代码 %}```cpp 分书问题 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
using namespace std;

const int maxn = 25;
char isLove[maxn][maxn];
bool isUsed[maxn];

int n;
int ans;

void init(){
ans = 0;
memset(isUsed,false,sizeof(isUsed));
}

//第 t 个人
void dfs(int t) {
if (t > n) {
ans++;
return;
}
bool ok = false;
for (int i = 1; i <= n; i++)
if (isLove[t][i]=='1' && !isUsed[i]) {
//for(int k=0;k<t;k++)
// printf(" ");
//printf("%d choose %d\n",t,i);
ok = true;
isUsed[i] = true;
dfs(t + 1);
isUsed[i] = false;
}
if (!ok)
return;
}

int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

while (scanf("%d",&n) != EOF) {
    init();
    for (int i = 1; i <= n; i++){
        scanf("%s",isLove[i]+1);
        //printf("%c%c%c%c%c\n",isLove[i][1],isLove[i][2],isLove[i][3],isLove[i][4],isLove[i][5]);
    }
    dfs(1);
    printf("%d\n",ans);
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}

{% endfold %}

推荐订阅源

OhYee 博客

题目

题解

代码