题目链接

舞会

题目描述

有 位男士和 位女士参加舞会。每一位男士都有若干心仪的女士，希望能与她们都跳一次舞。同样，每一位女士也有若干心仪的男士，也希望能与他们都跳一次舞。

在一首舞曲中，一个人最多只能与另一个人跳舞。

求最少需要准备多少首舞曲，才能满足所有人的心愿。

解题思路

这是一个可以利用图论模型解决的问题，其核心在于理解“满足所有人”的限制条件。

  1. 构建舞蹈关系：

    • 题目要求满足所有人的心愿。这意味着，如果男士 心仪女士 ，他们就需要跳一次舞；同样，如果女士 心仪男士 ，他们也需要跳一次舞。
    • 因此，一个舞蹈 (男士 ，女士 ) 需要被安排，只要满足以下两个条件之一即可：
      1. 男士 的心仪列表里有女士 。
      2. 女士 的心仪列表里有男士 。
    • 我们可以构建一个二分图，其中图的边代表所有需要完成的舞蹈。边的集合是所有男士心仪关系和女士心仪关系的并集。

  2. 寻找瓶颈：

    • 在一首舞曲中，一个人只能有一个舞伴。
    • 问题的瓶颈在于最“忙”的人，即需要参加最多舞蹈的人。例如，如果男士 总共需要和 位不同的女士跳舞，那么他至少需要 首歌的时间。
    • 因此，我们只需要计算出每个人（包括所有男士和女士）需要跳舞的总次数，然后找出这个次数的最大值，即为最少需要的舞曲数。

  3. 算法实现：

    • 在图论中，一个顶点需要参与的边的数量称为该顶点的度。问题就转化为了求这个关系图的最大度数。
    • 步骤： a. 使用一个二维布尔数组 required_dance[n+1][m+1] 来记录所有需要安排的舞蹈。初始化为 false。 b. 读入所有男士的心仪列表。对于每个心仪关系 (男士 ，女士 )，设置 required_dance[i][j] = true。 c. 读入所有女士的心仪列表。对于每个心仪关系 (女士 ，男士 )，同样设置 required_dance[i][j] = true。 d. 创建两个数组 man_degree[n+1] 和 woman_degree[m+1] 来记录每个人的度。 e. 遍历整个 required_dance 数组，如果 required_dance[i][j] 为 true，则将 man_degree[i] 和 woman_degree[j] 分别加一。 f. 最后，找出 man_degree 和 woman_degree 数组中的最大值，即为答案。

代码

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<bool>> required_dance(n + 1, vector<bool>(m + 1, false));

    // 读入男士的心仪列表
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            int woman_id;
            cin >> woman_id;
            required_dance[i][woman_id] = true;
        }
    }

    // 读入女士的心仪列表
    for (int i = 1; i <= m; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            int man_id;
            cin >> man_id;
            required_dance[man_id][i] = true;
        }
    }

    vector<int> man_degree(n + 1, 0);
    vector<int> woman_degree(m + 1, 0);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (required_dance[i][j]) {
                man_degree[i]++;
                woman_degree[j]++;
            }
        }
    }

    int max_degree = 0;
    for (int i = 1; i <= n; ++i) {
        max_degree = max(max_degree, man_degree[i]);
    }
    for (int i = 1; i <= m; ++i) {
        max_degree = max(max_degree, woman_degree[i]);
    }

    cout << max_degree << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        boolean[][] requiredDance = new boolean[n + 1][m + 1];

        // 读入男士的心仪列表
        for (int i = 1; i <= n; i++) {
            int k = sc.nextInt();
            for (int j = 0; j < k; j++) {
                int womanId = sc.nextInt();
                requiredDance[i][womanId] = true;
            }
        }

        // 读入女士的心仪列表
        for (int i = 1; i <= m; i++) {
            int k = sc.nextInt();
            for (int j = 0; j < k; j++) {
                int manId = sc.nextInt();
                requiredDance[manId][i] = true;
            }
        }

        int[] manDegree = new int[n + 1];
        int[] womanDegree = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (requiredDance[i][j]) {
                    manDegree[i]++;
                    womanDegree[j]++;
                }
            }
        }

        int maxDegree = 0;
        for (int i = 1; i <= n; i++) {
            maxDegree = Math.max(maxDegree, manDegree[i]);
        }
        for (int i = 1; i <= m; i++) {
            maxDegree = Math.max(maxDegree, womanDegree[i]);
        }

        System.out.println(maxDegree);
    }
}

import sys

def solve():
    try:
        line = sys.stdin.readline()
        if not line: return
        n, m = map(int, line.strip().split())

        required_dance = [[False for _ in range(m + 1)] for _ in range(n + 1)]

        # 读入男士的心仪列表
        for i in range(1, n + 1):
            prefs = list(map(int, sys.stdin.readline().strip().split()))
            if prefs:
                for woman_id in prefs[1:]:
                    required_dance[i][woman_id] = True

        # 读入女士的心仪列表
        for i in range(1, m + 1):
            prefs = list(map(int, sys.stdin.readline().strip().split()))
            if prefs:
                for man_id in prefs[1:]:
                    required_dance[man_id][i] = True
        
        man_degree = [0] * (n + 1)
        woman_degree = [0] * (m + 1)

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if required_dance[i][j]:
                    man_degree[i] += 1
                    woman_degree[j] += 1
        
        max_degree = 0
        for deg in man_degree:
            max_degree = max(max_degree, deg)
        for deg in woman_degree:
            max_degree = max(max_degree, deg)

        print(max_degree)

    except (IOError, ValueError):
        return

solve()

算法及复杂度

  • 算法：图论、最大度数

  • 时间复杂度：，其中 分别是男女士人数， 分别是所有心仪列表的长度总和。我们需要 来读取输入并构建关系矩阵，然后需要 来遍历矩阵计算度数。

  • 空间复杂度：。需要一个二维数组来存储所有的舞蹈关系。