题目大意:有 p 个学生和 n 门课 , 每一个门课程可以被多个学生选,问:在每个学生只能选一门课的情况下,能否使这 p 个学生每个人选的课程都不相同?
解题思路:这是一道简单的求最大匹配问题,只要求出此图的最大匹配,然后判断是否与 p 相等即可。
请看代码:
#include <iostream> #include <set> #include <algorithm> #include <map> #include <cstdio> #include <cstdlib> #include <stack> #include <cstring> #include <map> #include <vector> #include <string> #include <cmath> #define eps 1e-7 #define mem(a , b) memset(a , b , sizeof(a) ) using namespace std ; const int MAXN = 500 ; int linkx[MAXN] ; vector<int> G[MAXN] ; int p , n ; bool vis[MAXN] ; void chu() { mem(linkx , -1) ; int i ; for(i = 0 ; i <= p ; i ++) G[i].clear() ; } void init() { scanf("%d%d" , &p , &n) ; int i ; for(i = 1 ; i <= p ; i ++) { int d ; scanf("%d" , &d) ; int j ; for(j = 0 ; j < d ; j ++) { int t ; scanf("%d" , &t) ; G[i].push_back(t) ; } } } int dfs(int u) { int i ; for(i = 0 ; i < G[u].size() ; i ++) { int v = G[u][i] ; if(!vis[v]) { vis[v] = true ; if(linkx[v] == -1 || dfs(linkx[v])) { linkx[v] = u ; return 1 ; } } } return 0 ; } void solve() { int i ; int ans = 0 ; for(i = 1 ; i <= p ; i ++) { mem(vis , 0) ; ans += dfs(i) ; } if(ans == p) { puts("YES") ; } else { puts("NO") ; } } int main() { int T ; scanf("%d" , &T) ; while (T --) { chu() ; init() ; solve() ; } return 0; }