AOJ 863.分书问题
302
题目
已知有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; }