A27939. 分玩具
填空题
中等
知识点
题目描述
分玩具
题目描述
已知 n 位小朋友对 m 件玩具的喜好（n ≤ m），现要将 m 件玩具分给 n 位小朋友，每位小朋友只能分到 1 件玩具，每件玩具也最多只能分给 1 位小朋友，并且还要求每位小朋友都能分到自己喜欢的玩具。
本题请你对任意 n 和 m 尝试列出所有满足要求的方案。
输入
输入第一行给出两个正整数 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。
数据范围
n ≤ m ≤ 8
输入样例
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)参考答案
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
int a[10];
bool b[10];
bool c[10][10];
int n,m;
void func(int k);
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
cin>>c[i][j];
}
}
func(1);
return 0;
}
void func(int k)
{
if(k>n)
{
cout<<"(";
for(int i = 1;i<=n;i++)
{
cout<<a[i]<<",";
}
cout<<")"<<endl;
return;
}
for(int i = 1;i<=m;i++)
{
if(b[i] == 0 && c[k][i] == 1)
{
a[k] = i;
b[i] = 1;
func(k+1);
b[i] = 0;
}
}
}
上一题
下一题