题面

大秦为你打开题目传送门

题目描述

一共有 $N$ 个学生（从 $1$ 到 $N$ 编号）跟 $P$ 门课程（从 $1$ 到 $P$ 编号）,每位学生有自己感兴趣的课程，只能选自己感兴趣的课当课代表，

现在要求每个学生至多担任一门课代表，且一门课代表至多只能由一个学生担任，问是否每一门课能配到一个课代表。

思路

这不用想了把，，，，一眼二分图最大匹配模板题，，，，

代码

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
#include<bits/stdc++.h>
using namespace std;

int p, n;
int mp[110][310];

int vis[310];
int chk[310];

void Input() {
    scanf("%d%d", &p, &n);
    int m, x;
    for(int i = 1; i <= p; i++) {
        scanf("%d", &m);
        for(int j = 1; j <= m; j++) {
            scanf("%d", &x);
            mp[i][x] = 1;
        }
    }
}

int Dfs(int u) {
	for(int i = 1; i <= n; i++) {
		if(mp[u][i] && !chk[i]) {
			chk[i] = 1; 
			if(!vis[i] || Dfs(vis[i])) {
				vis[i] = u; 
				return 1; 
			}
		}
	}
	return 0; 
}

void Work() {
    int ans = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= p; i++) {
        memset(chk, 0, sizeof(chk));
        ans += Dfs(i);
    }
	if(ans == p) printf("YES\n"); 
	else printf("NO\n"); 
}

int main() {
    Input();
    Work();
    return 0;
}