[11376] 열혈 강호2

• 입력: 직원 수 N, 일의 개수 M, N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호
• 출력: 강호네 회사에서 할 수 있는 일의 개수
• 알고리즘: 이분매칭
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; vector<vector<int> > priority; vector<bool> visited; vector<int> task, tasks; bool dfs(int here) { if (visited[here]) return 0; visited[here] = true; int sz = priority[here].size(); for (int i = 0; i < sz; i++) { int there = priority[here][i]; //there 일을 의미 //이 일이 배정되어 있지 않거나 다른 사람이 이 일을 맡았는데 다른 것도 맡을 수 있을때 if (!task[there] || dfs(task[there])) { task[there] = here; //이 일을 내가 맡음 return true; } } return false; } int DFS(int here) { visited[here] = true; int sz = priority[here].size(); for (int i = 0; i < sz; i++) { int there = priority[here][i]; //there 일을 의미 //이 일이 배정되어 있지 않거나 다른 사람이 이 일을 맡았는데 다른 것도 맡을 수 있을때 if (!task[there] || dfs(task[there])) { task[there] = here; //이 일을 내가 맡음 if (++tasks[here] == 2) return 2; } } return tasks[here]; } int bmatch(const int n) { int ret = 0; for (int i = 1; i <= n; i++) { visited = vector<bool>(n + 1); ret += DFS(i); } return ret; } int main() { int n, m, s, room; scanf("%d%d", &n, &m); priority = vector<vector<int> >(n + 1); task = vector<int>(m + 1, 0); tasks = vector<int>(n + 1, 0); for (int i = 1; i <= n; i++) { scanf("%d", &s); for (int j = 0; j < s; j++) { scanf("%d", &room); priority[i].push_back(room); } } printf("%d\n", bmatch(n)); return 0; }
• 문제 참조: https://www.acmicpc.net/problem/11376