POJ 1469 COURSES（二分图最大匹配，裸题）

题目意思：
p门课，n个学生，每一门课都有若干学生可以当代表。当然，每一个学生最多只能是一门课的代表。
问：能否为每一门课都选出一个学生当代表。

本题要点：
1、二分图最大匹配：
左部节点：课程的编号；
右部节点：学生的编号；
用邻接矩阵存放 图，使用增光路算法求出最大匹配数。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 310;
int a[MaxN][MaxN], match[MaxN];
int T, p, n;
bool vis[MaxN];bool dfs(int x)
{
    for(int y = 1; y <= n; ++y){
    if(!a[x][y] || vis[y])continue;vis[y] = true;if(!match[y] || dfs(match[y])){
    match[y] = x;return true;}}return false;
}int main()
{
    int k, stu;scanf("%d", &T);while(T--){
    memset(a, 0, sizeof a);memset(match, 0, sizeof match);scanf("%d%d", &p, &n);for(int i = 1; i <= p; ++i){
    scanf("%d", &k);for(int j = 0; j < k; ++j){
    scanf("%d", &stu);a[i][stu] = 1;}}if(p > n){
    printf("NO\n");continue;}int ans = 0;for(int i = 1; i <= p; ++i){
    memset(vis, 0, sizeof vis);if(dfs(i))++ans;}if(ans == p){
    printf("YES\n");	}else{
    printf("NO\n");}}return 0;
}/* 2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1 *//* YES NO */