简答题
偏难
#13218
分玩具 已知 n 位小朋友对 m 件玩具的喜好(n ≤ m),现要将 m 件玩具分给 n 位小朋友,每位小朋友只能分到 1 件玩具,每件玩具也最多只能分给 1…
分玩具
已知 n 位小朋友对 m 件玩具的喜好(n ≤ m),现要将 m 件玩具分给 n 位小朋友,每位小朋友只能分到 1 件玩具,每件玩具也最多只能分给 1 位小朋友,并且还要求每位小朋友都能分到自己喜欢的玩具。
本题请你对任意 n 和 m 尝试列出所有满足要求的方案。
时间限制:5000
内存限制:65536
输入
输入第一行给出两个正整数 n 和 m(n ≤ m ≤ 8),即小朋友人数和玩具的数量。 随后 n 行,每行给出 m 个数字。其中第 i 行第 j 个数字为 1 表示第 i 位小朋友喜欢第 j 件玩具,为 0 则表示不喜欢。
输出
按升序列出所有满足要求的方案,格式为 (s1, … , sn)。其中 si 表示第 i 位小朋友分到了第 si 件玩具。 注:方案 (a1, … , an) < (b1, … , bn) 是指存在 1 ≤ k ≤ n,使得 ai = bi 对所有 1 ≤ i< k 成立,并且有 ak < bk。
样例输入
4 5 0 1 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1
样例输出
(2, 1, 3, 4) (2, 1, 3, 5) (2, 1, 4, 5) (2, 4, 1, 5) (2, 4, 3, 5) (5, 1, 3, 4) (5, 2, 1, 4) (5, 2, 3, 4)
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void backtrack(int k, int mask, vector<int>& path, vector<vector<int>>& res, const vector<vector<int>>& preferences) {
if (k == preferences.size()) {
res.push_back(path);
return;
}
for (int j : preferences[k]) {
if (!(mask & (1 << (j - 1)))) {
path.push_back(j);
backtrack(k + 1, mask | (1 << (j - 1)), path, res, preferences);
path.pop_back();
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> preferences(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int x;
cin >> x;
if (x == 1) {
preferences[i].push_back(j + 1); // 玩具编号从1开始
}
}
sort(preferences[i].begin(), preferences[i].end()); // 对每个小朋友的喜好进行排序
}
vector<vector<int>> res;
vector<int> path;
backtrack(0, 0, path, res, preferences);
sort(res.begin(), res.end());
for (const auto& vec : res) {
cout << "(";
for (size_t i = 0; i < vec.size(); ++i) {
if (i > 0) {
cout << ", ";
}
cout << vec[i];
}
cout << ")" << endl;
}
return 0;
}</pre>
这道题暂未补解析。