首页 > 试题广场 >

舞会

[编程题]舞会
  • 热度指数：1486 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解

今天，在冬木市举行了一场盛大的舞会。参加舞会的有n 位男士，从 1 到 n 编号；有 m 位女士，从 1 到 m 编号。对于每一位男士，他们心中都有各自心仪的一些女士，在这次舞会中，他们希望能与每一位自己心仪的女士跳一次舞。同样的，对于每一位女士，她们心中也有各自心仪的一些男士，她们也希望能与每一位自己心仪的男士跳一次舞。在舞会中，对于每一首舞曲，你可以选择一些男士和女士出来跳舞。但是显然的，一首舞曲中一位男士只能和一位女士跳舞，一位女士也只能和一位男士跳舞。由于舞会的时间有限，现在你想知道你最少需要准备多少首舞曲，才能使所有人的心愿都得到满足？


输入描述:
第一行包含两个整数n,m，表示男士和女士的人数。1≤n,m≤ 1000
接下来n行，
第i行表示编号为i的男士有ki个心仪的女生
然后包含ki个不同的整数分别表示他心仪的女士的编号。
接下来m行，以相同的格式描述每一位女士心仪的男士。


输出描述:
一个整数，表示最少需要准备的舞曲数目。
示例1

输入

2 3
1 1
2 2 3
0
0
0

输出

2
示例2

输入

3 3
2 1 2
2 1 3
2 2 3
1 1
2 1 3
2 2 3

输出

2

说明

对于样例2，我们只需要两首舞曲，第一首舞曲安排（1,1），（2,3），（3,2）；第二首舞曲安排（1,2），(2,1)，（3,3）。
算法知识视频讲解
添加回答
Python
TimeMac头像 TimeMac 
n, m = map(int, input().split())
heartbeat = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in list(map(int, input().split()))[1:]:
        if not heartbeat[i][j]:
            heartbeat[i][j] = 1
            heartbeat[i][0] += 1
            heartbeat[0][j] += 1
for i in range(1, m + 1):
    for j in list(map(int, input().split()))[1:]:
        if not heartbeat[j][i]:
            heartbeat[j][i] = 1
            heartbeat[j][0] += 1
            heartbeat[0][i] += 1
print(max(max(heartbeat[0]), max(heartbeat[0][j] for j in range(1, n + 1))))
编辑于 2019-03-26 23:49:23 回复(0)
向宇回桌头像 向宇回桌 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        ArrayList<Set<Integer>> man = new ArrayList<>(), women = new ArrayList<>();
        for (int i=0; i<=n; i++) { man.add(new HashSet<>()); }
        for (int i=0; i<=m; i++) { women.add(new HashSet<>()); }
        for (int i=1; i<=n; i++) {
            int pn = sc.nextInt();
            for (int j=0; j<pn; j++) {
                int wp = sc.nextInt();
                man.get(i).add(wp);
                women.get(wp).add(i);
            }
        }
        for (int i=1; i<=m; i++) {
            int pn = sc.nextInt();
            for (int j=0; j<pn; j++) {
                int wp = sc.nextInt();
                women.get(i).add(wp);
                man.get(wp).add(i);
            }
        }
        int ans = 0;
        for (int i=1; i<=n; i++) {
            ans = Math.max(man.get(i).size(), ans);
        }
        for (int i=1; i<=m; i++) {
            ans = Math.max(women.get(i).size(), ans);
        }
        System.out.println(ans);
    }
}
发表于 2019-04-07 20:37:34 回复(0)
❄️201902042025939头像 ❄️201902042025939
我觉得可以把这个题目当作一个棋盘，你把舞伴当作棋子，男女两个棋盘，再把所有组合都当作棋子摆在你规定的位置上，一次去掉一个男女位置相同的棋子而且下一次去掉的棋子必须是和前面所有去掉的棋子是不同行不同列的，最后计算去掉所有棋子的步骤，选最少。
编辑于 2019-02-07 13:37:50 回复(0)
wylu头像 wylu 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), m = Integer.parseInt(strs[1]);

        //女士受男士心仪的数量的最大值
        HashMap<String, Integer> map1 = new HashMap<>();
        int max1 = count(br, map1, n); //男士心仪的女士的个数的最大值
        
        //男士受女士心仪的数量的最大值
        HashMap<String, Integer> map2 = new HashMap<>();
        int max2 = count(br, map2, m); //女士心仪的男士的个数的最大值

        int res = Math.max(max1, max2);
        for (String str : map1.keySet()) res = Math.max(res, map1.get(str));
        for (String str : map2.keySet()) res = Math.max(res, map2.get(str));
        System.out.println(res);
    }

    private static int count(BufferedReader br, HashMap<String, Integer> map,
                              int len) throws IOException {
        int maxNum = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            String[] strs = br.readLine().split(" ");
            maxNum = Math.max(maxNum, strs.length - 1);
            for (int j = 1; j < strs.length; j++) {
                if (map.containsKey(strs[j])) map.put(strs[j], map.get(strs[j]) + 1);
                else map.put(strs[j], 1);
            }
        }
        return maxNum;
    }
}

编辑于 2019-01-17 21:21:29 回复(0)
静かな小布头像 静かな小布
注意了，此题并非计算每个人心仪对象数量的最大值，而是每个人心仪对象加被心仪对象数量（不重复计算）的最大值！下方测试用例应输出2而非1：
2 1
1 1
0
1 2

发表于 2019-01-18 15:53:21 回复(2)
C/C++
一个好听的名字头像 一个好听的名字 
#include <iostream>
using namespace std;
int ans[1001][1001] = {0};   //设立一个二维数组用来记录心仪情况
int main()
{
    int n = 0, m = 0, i = 0, j = 0, x = 0, max_wu = 0;
    cin >> n >> m;
    int t = m + n;                   //总共t个人
    for (i = 1; i <= n; i++)   //先对男生，即数组的前n个进行数据的输入
    {
        cin >> j;                    //心仪j个人
        for (int k = 0; k < j; k++)   //分别是 哪些个 女生进行标记
        {
            cin >> x;
            ans[i][n + x] = 1;   //注意，在这里标记的时候，因为按照行来女生是在男生后面，列对称
        }
    }
    for (; i <= t; i++)  //然后对女生的行数的数据进行输入
    {
        cin >> j;
        for (int k = 0; k < j; k++)
        {
            cin >> x;
            ans[i][x] = 1;
        }
    }
    for (i = 1; i <= t; i++) //从第一个人开始，进行最多心仪数的判断
    {             //注意，对于每一个人来说，自己对对方心仪，对方也对自己心仪算作一次
        int temp = 0;           //其它情况，即只要是单向的心仪也均算做一次
        int up_line = 0;
        if (i <= n)    //如果目前是男生，则只考虑女生，使j调到女生第一个
        {
            j = n + 1;
            up_line = t;
        }
        else       //如果目前是女生，则只考虑男生，调到男生第一个，且上限为最后一个男生
        {
            j = 1;
            up_line = n;
        }
        for (; j <= up_line; j++)
        {
            if (ans[i][j] == 1)
            {
                temp = temp + 1;
            }
            else
            {
                if (ans[j][i] == 1)
                temp = temp + 1;
            }
        }
        if (max_wu < temp)       //进行在线的最大舞曲次数的更新
        {
            max_wu = temp;
        }
    }
    cout << max_wu << endl;   //最后输出最大的舞曲次数
    return 0;
}

编辑于 2019-04-10 21:52:32 回复(6)
会意头像 会意

运行时间：3ms
占用内存：484k
基本思想就是构建二维数组存储男女配对情况。有配对为1，无配对为0，然后找出最大值。
评论区有人说不需要存储，我觉得是他们没有考虑到一个男士除了有他自己心仪的女性对象外，还有可能是其他女士的心仪对象，并且这两者之间可能会有重复，所以我觉得还是要全部配对完毕后，再统计最大值。代码如下：注释已经很详细了。

#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>

using namespace std;

int main() {
    //男  女
    int m, n;
    //构建二维数组存储男女配对情况，无配对为0，有配对为1
    vector<vector<int> > dance_list;
    scanf_s("%d", &n);
    scanf_s("%d", &m);
    //设置行容量
    dance_list.resize(n);
    //读取男士心仪对象
    for (int i = 0; i < n; ++i) {
        int total, k;
        scanf_s("%d", &total);
        //设置列容量，并将所有值初始化为0
        dance_list[i].resize(m, 0);
        //记录男士配对情况
        for (int j = 0; j < total; ++j) {
            scanf_s("%d", &k);
            dance_list[i][k - 1] = 1;
        }
    }
    //读取女士心仪对象
    for (int j = 0; j < m; ++j) {
        int total, k;
        scanf_s("%d", &total);
        //记录女士配对情况
        for (int i = 0; i < total; ++i) {
            scanf_s("%d", &k);
            dance_list[k - 1][j] = 1;
        }
    }
    //男士最多跳舞对象人数
    int max_man = 0;
    //女士最多跳舞对象人数
    int max_woman = 0;
    //每位男士跳舞对象人数
    int row_sum = 0;
    //每位女士跳舞对象人数
    vector<int> col_sum;
    //设置容量，并将所有值初始化为0
    col_sum.resize(m, 0);
    for (int i = 0; i < n; ++i) {
        //统计每位男士跳舞对象人数
        row_sum = std::accumulate(dance_list[i].begin(), dance_list[i].end(), 0);
        //更新男士最多跳舞对象人数
        max_man = std::max(max_man, row_sum);
        //统计每位女士跳舞对象人数
        for (int j = 0; j < m; ++j) {
            col_sum[j] += dance_list[i][j];
        }
    }
    //找出女士最多跳舞对象人数
    vector<int>::iterator max_female = std::max_element(begin(col_sum), end(col_sum));
    max_woman = *max_female;
    //比较最大人数
    int result = std::max(max_man, max_woman);
    printf("%d", result);
    system("pause");
    return 0;
}
发表于 2019-03-27 15:42:25 回复(1)
acvv_khalil头像 acvv_khalil 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

int n1, n2;
int g[N][N];

int main() {
    cin >> n1 >> n2;
    for(int i=1; i<=n1; i++) {
        int t;
        cin >> t;
        while(t--) {
            int j;
            cin >> j;
            g[i][j] = 1;
        }
    }
    for(int i=1; i<=n2; i++) {
        int t;
        cin >> t;
        while(t--) {
            int j;
            cin >> j;
            g[j][i] = 1;
        }
    }
    
    int res = 0;
    for(int i=1; i<=n1; i++) {
        int t = 0;
        for(int j=1; j<=n2; j++) {
            if(g[i][j]) t++;
        }
        res = max(res, t);
    }
    cout << res << endl;
    return 0;
}

发表于 2021-10-29 17:14:26 回复(0)
500cc头像 500cc
男生心仪矩阵和女生心仪矩阵相加（0+0=0，0+1=1,1+1=1）
最后计算列和，取列和向量里的最大值 
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int arr[m][n];
    for(int i=0;i<n;i++){
        for(int k=0;k<m;k++){
            arr[k][i]=0;
        }
    }
    
    int temp1,temp2;
    for(int i=0;i<n;i++){
        cin>>temp1;
        for(int k=0;k<temp1;k++){
            cin>>temp2;
            arr[temp2-1][i]=1;
        }
    }
    
    for(int i=0;i<m;i++){
        cin>>temp1;
        for(int k=0;k<temp1;k++){
            cin>>temp2;
            arr[i][temp2-1]=1;
        }
    }
    
    int sum[n];
    for(int i=0;i<n;i++){
        sum[i]=0;
        for(int k=0;k<m;k++){
            sum[i]=sum[i]+arr[k][i];
        }
    }
    
    sort(sum,sum+n);
    cout<<sum[n-1]<<endl;
    return 0;
}


发表于 2021-07-21 16:15:31 回复(0)
siku头像 siku
东木市又是核平的一天
发表于 2020-07-07 10:35:08 回复(0)
彡(￣_￣；)彡头像 彡(￣_￣；)彡
直接心仪对象最多的跳的最多
n,m=map(int, input().split())
x={}
for i in range(n+m):
    x[i]=list(map(int,input().split()))
    z=max(x[i][0],z)
print(z)
发表于 2020-06-23 17:23:13 回复(0)
C/C++
海问香12138头像 海问香12138 
#include <stdio.h>

#define MAXN 1010

int n,m;
int a[MAXN][MAXN];

int main()
{
	int i,j,t,sum,max=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&sum);
		for(j=0;j<sum;j++)
		{
			scanf("%d",&t);
			a[i][t] = 1;
			a[t][i] = 1;
		}
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&sum);
		for(j=0;j<sum;j++)
		{
			scanf("%d",&t);
			a[i][t] = 1;
			a[t][i] = 1;
		}
	}
	for(i=1;i<=n;i++)
	{
		sum = 0;
		for(j=1;j<=m;j++)
			if(a[i][j])
				sum++;
		if(sum>max)
			max = sum;
	}
	printf("%d\n",max);
	return 0;
}

发表于 2019-08-20 10:05:42 回复(0)
冬雪香莹头像 冬雪香莹
将输入保存成二维数组的形式，行数为n代表男生，列数为m代表女生，记录时只需将心仪对象位置标记为1，保证同时被心仪时不重复标记。
只要寻找每行和每列中“1”出现的最大次数即可，即每个人心仪对象加被心仪对象数量的最大值。
因为只要保证最忙的那个人能跳完就行，其他人随意搭配。 
#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int dp[1001][1001];
    for(int i=1;i<=n;i++)
    {
        int nn;
        cin>>nn;
        if(nn)
        {
            int nk;
            for(int j=0;j<nn;j++)
            {
                cin>>nk;
                dp[i][nk]=1;
            }
        }
    }
        for(int i=1;i<=m;i++)
    {
        int mm;
        cin>>mm;
        if(mm)
        {
            int mk;
            for(int j=0;j<mm;j++)
            {
                cin>>mk;
                dp[mk][i]=1;
            }
        }
    }
    int max=0;
    for(int i=1;i<=n;i++)
    {
        int tmp=0;
        for(int j=1;j<=m;j++)
        {
            if(dp[i][j]==1)
            {
                tmp++;
            }
        }
        if(tmp>max)
        {
            max=tmp;
        }
    }
    for(int j=1;j<=m;j++)
    {
        int tmp=0;
        for(int i=1;i<=n;i++)
        {
            if(dp[i][j]==1)
            {
                tmp++;
            }
        }
        if(tmp>max)
        {
            max=tmp;
        }
    }
    cout<<max<<endl;
}

发表于 2019-05-31 11:04:47 回复(0)
风雨也从容头像 风雨也从容
#include<stdio.h>
int main()
{
    int a[2];
    scanf("%d%d", a+0, a+1);
    int an[4][1000] = {0};
    for(int j = 0; j < 2; ++j) {
        for(int i = 0; i < a[j]; ++i) {
            int num1, num2;
            scanf("%d", &num1);
            an[j*2][i] = num1;
            while(num1--) {
                scanf("%d", &num2);
                ++an[j*2+1][num2-1];
            }
        }
    }
    int max = 0;
    for(int j = 0; j < 2; ++j)
        for(int i = 0; i < a[j]; ++i){
            if(an[j][i] > max)
                max = an[j][i];
            if(an[3-j][i] > max)
                max = an[3-j][i];
        }
    printf("%d\n", max);
    return 0;
}
发表于 2019-05-04 18:33:31 回复(0)
Aterfer头像 Aterfer

大概说一下自己的思路：选择男生或者女生为基准，只需要统计出所有男生（女生）需要上场的次数，然后最大的那个就是目标值了；

#include <iostream>

#include <vector>
using namespace std;

const int maxn=2010;
typedef struct man
{
int num;
vector<int>ves;
};
man aa[maxn];
int is_in(int man_num,int wman_num)
{
for(int i=0;i<aa[man_num].ves.size();i++)
if(aa[man_num].ves[i]==wman_num) return 1;
return -1;
}
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
aa[i].num=k;
while(k--)
{
int code;
cin>>code;
aa[i].ves.push_back(code);
}
}
for(int i=1;i<=m;i++)
{
int kk;
cin>>kk;
while(kk--)
{
int man_num;
cin>>man_num;
if(is_in(man_num,i)==-1) aa[man_num].num ++;
}
}
int max=0;
for(int i=1;i<=n;i++)
{
if(aa[i].num>max) max=aa[i].num;
}
cout<<max<<endl;
return 0;
}

发表于 2019-04-22 16:11:01 回复(0)
osingle头像 osingle
去重考虑用set，然后统计最多的一个人有多少个女伴要跳舞，取个最大值可以得到解。
#include<iostream>
#include<set>
using namespace std;

int main(){
    set<pair<int,int> > reSet;
    int man,woman;
    cin >> man >> woman;
    for(int i = 0 ; i < man;i++){
        int n;
        cin >> n;
        for(int j = 0 ;  j < n ; j++){
            int tmp;
            cin >> tmp;
            reSet.insert(make_pair(i + 1,tmp));
        }
    }
    for(int i = 0 ; i < woman;i++){
        int n;
        cin >> n;
        for(int j = 0 ;  j < n ; j++){
            int tmp;
            cin >> tmp;
            reSet.insert(make_pair(tmp,i + 1));
        }
    }
    int re[man];
    for(int i = 0; i < man;i++){
        re[i] = 0;
    }
    for(set<pair<int,int> >::iterator it = reSet.begin();it != reSet.end(); it++){
        re[(it->first) - 1]++;
    }
    int max = 0;
    for(int i = 0 ; i < man ;i++){
        max = max > re[i] ? max:re[i];
    }
    cout << max << endl;
}

发表于 2019-03-30 20:12:11 回复(0)
黄宗文头像 黄宗文 
n, m = map(int, input().split())
men = 0
for i in range(n):
    men = max(men, int(input().split()[0]))
lady = 0
for j in range(m):
    lady = max(lady, int(input().split()[0]))
print(max(men, lady))            # 很没意思的题

发表于 2019-03-27 16:16:55 回复(0)
Python
offer你快来啊头像 offer你快来啊
比较暴力啊，就是求解A方的心仪对象B的心仪对象的人数，然后取其中最大值。
n,m=list(map(int, input().split(" ")))
fe,ma=[],[]
for i in range(n):
    ma.append(list(map(int, input().split(" "))))
for i in range(m):
    fe.append(list(map(int, input().split(" "))))
s=[]
for i in range(len(fe)):
    if fe[i][0]==0:
        s.append(0)
    else:
        smax = 0
        for j in fe[i][1:]:
            smax = max(smax,ma[j-1][0])
        s.append(smax)
for i in range(len(ma)):
    if ma[i][0]==0:
        s.append(0)
    else:
        smax = 0
        for j in ma[i][1:]:
            smax = max(smax,fe[j-1][0])
        s.append(smax)    
print (max(s))
发表于 2019-03-24 21:34:40 回复(0)
我是谁chspac头像 我是谁chspac

无需数组，只要找到心仪数最大即可....

import java.util.*;

public class Main{
public static void main(String [] arg){
int n,m,tem;
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
int row_max=0,col_max=0;
for(int i=0;i<n;i++){
tem=sc.nextInt();
if(tem>row_max)row_max=tem;
for(int j=0;j<tem;j++){
sc.nextInt();
}
}
for(int i=0;i<m;i++){
tem=sc.nextInt();
if(tem>col_max)col_max=tem;
for(int j=0;j<tem;j++){
sc.nextInt();
}
}

    //row
    if(col_max>row_max)System.out.println(col_max);
    else System.out.println(row_max);

}

}

发表于 2019-03-24 18:38:52 回复(0)
C/C++
brutalkiller13头像 brutalkiller13
此题创建一个二维数组记录所有的心仪对数，然后计算数组每行和每列最多的心仪对数，即为所需最少的歌曲数。
我的代码构建了二维数组记录所有的心仪对数，但是计算歌曲数的方法并不是计算数组中每行和每列最多的心仪对数。我前面的代码count参数计算出了所有的心仪对数总数。然后while每循环一次就会减去一首歌中最多匹配心仪对跳舞的总数，最后count为0，表示所有的心仪对都跳完了，while的循环数就是歌曲总数。
#include <iostream>
using namespace std;

int main()
{
    int n,m;
    int **a;
    int count = 0;
    int songs = 0;
    cin >> n >> m;
    a = new int*[n+1];
    for(int i=1;i<n+1;i++)
    {
        a[i] = new int[m+1];
        for(int j=1;j<=m;j++)
            a[i][j]=0;
    }
    for(int i=1;i<=n;i++)
    {
        int num;
        cin >> num;
        for(int j=0;j<num;j++)
        {
            int k;
            cin >> k;
            a[i][k]=1;
            count++;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int num;
        cin >> num;
        for(int j=0;j<num;j++)
        {
            int k;
            cin >> k;
            if(a[k][i]==0)
            {
                a[k][i]=1;
                count++;
            }
        }
    }
    int* women = new int[m+1];
    while(count)
    {
        for(int i=1;i<=m;i++)
            women[i]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(a[i][j]==1 && women[j]==0)
                {
                    count--;
                    a[i][j]=0;
                    women[j]=1;
                    break;
                }
            }
        }
        songs++;
    }
    cout << songs;
    return 0;
}
发表于 2019-02-27 11:32:42 回复(0)
提交观点

问题信息

贪心 图
上传者：小小
难度：
24条回答 7451浏览

热门推荐

通过挑战的用户

查看代码

相关试题

舞会

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号