A30972.【搜索】【回溯】分书问题

很容易看出是搜索题，易得代码

1.0
#include <iostream>
using namespace std;
const int N = 20;
int n , tot;
bool like[N + 5][N + 5];
bool used[N + 5];
void DFS(int dpt)
{
	if (dpt > n)
	{
		++tot;
		return;
	}
	for (int i = 1 ; i <= n ; ++i)
	{
		if (like[dpt][i] == true && used[i] == false)
		{
			used[i] = true;
			DFS(dpt + 1);
			used[i] = false;
		} 
	}
}
int main()
{
	cin >> n;
	for (int i = 1 ; i <= n ; ++i)
		for (int j = 1 ; j <= n ; ++j)
			cin >> like[i][j];
	DFS(1);
	cout << tot << endl;
	return 0;
} 

还有优化空间，我们可以启发式排序优化（在选择上贪心优化），按照喜欢的书数量从小到大排序，再按每一个人喜欢的书中按书出现的频率从小到大排序，实现提前剪枝，从而缩小搜索树宽度。

2.0
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 20;
bool cmp(const vector <int>& a , const vector <int>& b){return a.size() <= b.size();}
int cnt[N + 5];
bool cmp2(const int a , const int b){return cnt[a] <= cnt[b];}
char like[N + 5][N + 5];
vector <int> one[N + 5];
bool used[N + 5];
int n , tot;
void DFS(int dpt)
{
	if (dpt > n)
	{
		++tot;
		return;
	}
	for (auto w : one[dpt])
	{
		if (used[w] == false)
		{
			used[w] = true;
			DFS(dpt + 1);
			used[w] = false;
		}
	}
}
int main()
{
	cin >> n;
	for (int i = 1 ; i <= n ; ++i)
	{
		for (int j = 1 ; j <= n ; ++j)
		{
			cin >> like[i][j];
			if (like[i][j] == '1')
			{
				++cnt[j];
				one[i].push_back(j);
			}
		}
	}
	sort(one , one + n + 1 , cmp);
	for (int i = 1 ; i <= n ;++i)
		sort(one[i].begin() , one[i].end() , cmp2);
	DFS(1);
	cout << tot << endl;
	return 0;
}