https://www.acmicpc.net/problem/2188
2188번: 축사 배정
농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해
www.acmicpc.net
|
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
|
#include <iostream>
#include <string.h>
#define NMAX 205
using namespace std;
int n, m, s, si;
int inp[NMAX][NMAX];
int visit[NMAX], b_match[NMAX];
bool dfs(int k) {
if(visit[k]) return 0;
visit[k] = 1;
for(int work=1;work<=m;work++) {
if(!inp[k][work]) continue;
if(!b_match[work] or dfs(b_match[work])) {
b_match[work] = k;
return 1;
}
}
return 0;
}
int bmatch() {
int ret=0;
for(int i=1;i<=n;i++) {
memset(visit, 0, sizeof(visit));
if(dfs(i)) ret++;
}
return ret;
}
int main() {
cin >> n >> m;
for(int i=1;i<=n;i++) {
cin >> s;
for(int j=1;j<=s;j++) {
cin >> si;
inp[i][si] = 1;
}
}
cout << bmatch();
}
|
cs |