题解

涉及知识点

1. 二分图匹配

   • 将课程和时间段建模为二分图：
     • 左节点：课程
     • 右节点：时间段 $(p, q)$
   • 使用匈牙利算法（Hungarian Algorithm）求最大匹配。

2. 冲突处理

   • 每门课程只需匹配一个时间段，且不同课程的时间段不能重复。

解法代码（C++）

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 300;
const int MAXT = 7 * 12 + 5;

vector<int> G[MAXN];  // 课程 -> 可分配的时间段
int match[MAXT];      // 时间段 -> 匹配的课程
bool vis[MAXT];       // 访问标记

bool dfs(int u) {
    for (int v : G[u]) {
        if (!vis[v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n;
    while (cin >> n) {
        // 初始化
        for (int i = 0; i < n; ++i) G[i].clear();
        memset(match, -1, sizeof(match));

        // 输入课程信息
        for (int i = 0; i < n; ++i) {
            int t;
            cin >> t;
            while (t--) {
                int p, q;
                cin >> p >> q;
                int time_slot = (p - 1) * 12 + q;  // 将(p,q)映射为唯一整数
                G[i].push_back(time_slot);
            }
        }

        // 匈牙利算法求最大匹配
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            memset(vis, false, sizeof(vis));
            if (dfs(i)) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

代码解释

1. 输入处理：

   • 将每个课程的时间段 $(p, q)$ 映射为唯一整数（如周二第7节 = $1 \times 12 + 7 = 19$）。

2. 匈牙利算法：

   • dfs(u)：尝试为课程 u 分配一个未冲突的时间段。
   • match[v]：记录时间段 v 分配的课程编号。

3. 结果输出：

   • 最大匹配数即为可选课程的最大数量。

复杂度分析

• 时间复杂度：$O(n \times m)$，其中 $n$ 是课程数，$m$ 是时间段总数（最多84）。
• 空间复杂度：$O(n + m)$，用于存储图和匹配数组。

总结

本题通过 二分图最大匹配 模型，将课程选择问题转化为图论问题，利用匈牙利算法高效求解。关键在于将课程和时间段建模为二分图的两部分节点，并确保匹配不冲突。