[1298] 노트북의 주인을 찾아서

• 입력: 노트북이 섞인 날 어제 노트북을 구입한 사람의 수 N(1<=N<=100)과 노트북 예상의 개수 M(0<=M<=5,000), M+1번째 줄 까지는 각각 한 줄마다 a b가 주어지는데, 이는 a번 사람이 b번 노트북을 자신의 것 이라고 생각한다는 의미를 갖는다.
• 출력: 최대로 만족될 수 있는 사람 수
• 알고리즘: 이분매칭
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; vector<vector<int> > priority; vector<bool> visited; vector<int> notebook; bool dfs(int here) { if (visited[here]) return false; visited[here] = true; int sz = priority[here].size(); for (int i = 0; i < sz; i++) { int there = priority[here][i]; if (!notebook[there] || dfs(notebook[there])) { notebook[there] = here; return true; } } return false; } int bmatch(const int n) { int ret = 0; for (int i = 1; i <= n; i++) { visited = vector<bool>(n + 1); if (dfs(i)) ret++; } return ret; } int main() { int n, m, a, b; scanf("%d%d", &n, &m); priority = vector<vector<int> >(n + 1); visited = vector<bool>(n + 1); notebook= vector<int>(m + 1, 0); for (int i = 0; i < m; i++){ scanf("%d%d", &a, &b); priority[a].push_back(b); } printf("%d\n", bmatch(n)); return 0; }
• 문제참고:https://www.acmicpc.net/problem/1298