题目描述
n个学生去p个课堂，每一个学生都有自己的课堂，并且每个学生只能去一个课堂，题目要求能够安排每一个课堂都有人吗？
输入格式
第一行是测试数据的个数，
每组测试数据的开始分别是p和n，
接着p行，每行的开始是这个课堂的学生人数m，接着m个数代表该课堂的学生编号
输出格式
如果该组数据能够这样安排就输出YES，否则输出NO。
输入样例
2
3 3
3 1 2 3
2 1 2
1 1
3 3
2 1 3
2 1 3
1 1
输出样例
YES
NO
说明
对于100%的数据，$n\le 100,m\le 20000$
Solution
裸的二分图最大匹配。
二分图匹配n倍经验
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 10010
namespace STman {
inline char gc(){
#ifdef ONLINE_JUDGE
static char now[1 << 16], *S, *T;
if (T == S) {T = (S = now) + fread(now, 1, 1 << 16, stdin); if (T == S) return EOF;}
return *S++;
#else
return getchar();
#endif
}
template <typename Tp>
inline void read(Tp &x) {
Tp f = 1;x = 0;
char k = gc();
while (k < '0' || k > '9') {if (k == '-') f = -1;k = gc();}
while (k >= '0' && k <= '9') {x = x * 10 + k - '0';k = gc();}
x = x * f;
}
template <typename Tp>
inline void write(Tp x) {
if (x < 0) putchar('-') , x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename Tp>
inline Tp max(Tp a , Tp b) {
if (a > b) return a;
else return b;
}
template <typename Tp>
inline Tp min(Tp a , Tp b) {
if (a < b) return a;
else return b;
}
template <typename Tp>
inline void swap(Tp &a , Tp &b) {
Tp t = a;
a = b;
b = t;
}
template <typename Tp>
inline Tp abs(Tp &a) {
if (a < 0) return -a;
else return a;
}
inline void sp() {
putchar(32);
}
inline void et() {
putchar(10);
}
}
using namespace STman;
struct Edge {
int v, nx;
}e[MAXN];
int head[MAXN], ecnt, n, t, m, mch[MAXN], vis[MAXN], p, x, tot;
void add(int f, int t) {
e[++ecnt] = (Edge) {t, head[f]};
head[f] = ecnt;
}
bool Hungary(int k, int t) {
for (int i = head[k]; i; i = e[i].nx) {
int to = e[i].v;
if (vis[to] != t) {
vis[to] = t;
if (!mch[to] || Hungary(mch[to], t)) {
mch[to] = k;
return 1;
}
}
}
return 0;
}
int main() {
read(t);
while (t--) {
read(n), read(m);
memset(head, 0, sizeof(head));
memset(mch, 0, sizeof(mch));
memset(vis, 0, sizeof(vis));
ecnt = 0, tot = 0;
for (int i = 1; i <= n; i++) {
read(p);
while (p--) {
read(x);
add(i, x);
}
}
if (n > m) {
puts("NO");
continue;
}
for (int i = 1; i <= n; i++) {
if (Hungary(i, i)) {
tot++;
}
}
if (tot == n) {
puts("YES");
}
else {
puts("NO");
}
}
}
|
