题意分析

题目描述了一个学生选课系统的匹配问题：

• 有P门课程和N个学生
• 每个学生可以选修0到多门课程
• 需要判断是否存在一个由P个学生组成的委员会，满足：
  1. 每个学生代表一门不同的课程（该学生必须选修该课程）
  2. 每门课程都有且只有一个学生代表

这实际上是一个典型的二分图匹配问题：

• 将课程视为左部节点
• 将学生视为右部节点
• 如果学生j选修了课程i，则建立一条边i→j
• 问题转化为求该二分图的完美匹配（大小为P的匹配）

解题思路

1. 建模为二分图匹配：

   • 课程集合作为左部（大小为P）
   • 学生集合作为右部（大小为N）
   • 建立课程到选修该课程的学生的边

2. 使用匈牙利算法：

   • 这是解决二分图匹配问题的经典算法
   • 时间复杂度为O(P*E)，其中E是边数
   • 对于本题P≤100，N≤300，完全在可接受范围内

3. 算法步骤：

   • 初始化匹配数组match[N]，记录每个学生的匹配课程
   • 对每门课程进行DFS，寻找增广路径
   • 如果找到增广路径就增加匹配数
   • 最终匹配数等于P则存在解

4. 优化考虑：

   • 使用邻接表存储图结构
   • 每次DFS前重置访问标记
   • 及时终止不必要的搜索

5. 边界情况处理：

   • 当某门课程没有学生选修时直接返回NO
   • 学生数N必须≥P（否则直接NO）

这个解法充分利用了二分图匹配的性质，通过匈牙利算法高效地解决了问题，在给定的数据范围内表现良好。

C++ 代码实现

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

const int MAXP = 105;
const int MAXN = 305;

vector<int> course[MAXP];  // 每个课程的学生列表
bool visited[MAXN];        // 标记学生是否被选
int match[MAXN];           // 学生匹配的课程
int P, N;

bool bpm(int u) {
    for (int v : course[u]) {
        if (!visited[v]) {
            visited[v] = true;
            if (match[v] == -1 || bpm(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

bool can_form_committee() {
    memset(match, -1, sizeof(match));
    
    for (int u = 1; u <= P; ++u) {
        memset(visited, false, sizeof(visited));
        if (!bpm(u)) {
            return false;
        }
    }
    return true;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> P >> N;
        
        // 初始化
        for (int i = 1; i <= P; ++i) {
            course[i].clear();
        }
        
        // 读取输入
        for (int i = 1; i <= P; ++i) {
            int count;
            cin >> count;
            for (int j = 0; j < count; ++j) {
                int student;
                cin >> student;
                course[i].push_back(student);
            }
        }
        
        if (can_form_committee()) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

代码说明

1. 数据结构：

   • 使用邻接表graph存储课程到学生的关系
   • match数组记录每个学生的匹配课程
   • visited数组用于DFS时的访问标记

2. 匈牙利算法实现：

   • dfs(u)函数尝试为课程u寻找匹配的学生
   • 通过递归寻找增广路径来更新匹配

3. 主流程：

   • 读取输入数据并构建邻接表
   • 初始化匹配数组
   • 对每门课程执行匈牙利算法
   • 统计匹配成功的课程数
   • 判断并输出结果

4. 优化：

   • 使用快速输入输出
   • 及时清空访问标记
   • 邻接表存储节省空间

该实现的时间复杂度为O(P*E)，其中E是边数，完全适用于题目给定的数据范围(P≤100,N≤300)。