题目

点击显/隐题目

已知有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

题解

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

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

代码

点击显/隐代码

/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <cstring>
#include <iostream>
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;
}

OhYee