AOJ 863.分书问题

183


题目



点击显/隐题目

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


1




题解


暴力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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论