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

문제 출처 :

https://www.acmicpc.net/problem/1298

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭 :: http://www.crocus.co.kr/499

이분 매칭을 의미하는 기본적인 문제이다.

위의 이분 매칭 링크를 통해 내용을 이해하고 그 코드를 기반으로 작성한다면 쉽게 풀 수 있는 문제이다.

유사 문제로 [2188번] 축사 배정 :: http://www.crocus.co.kr/498의 문제도 이 코드로 해결이 가능하다.

소스 코드 : 

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

#include <iostream> #include <vector>   using namespace std;   #define MAX_N 200 #define MAX_M 200   int n, m;   bool adj[MAX_N][MAX_M];   vector<int> aMatch, bMatch; vector<bool> visited;   bool dfs(int a) {     if (visited[a])         return false;       visited[a] = true;       for (int b = 0; b < m; b++)         if (adj[a][b])             if (bMatch[b] == -1 || dfs(bMatch[b]))             {                 aMatch[a] = b;                 bMatch[b] = a;                   return true;             }          return false; }   int bipartiteMatch() {     aMatch = vector<int>(n, -1);     bMatch = vector<int>(m, -1);       int size = 0;       for (int start = 0; start < n; start++)     {         visited = vector<bool>(n, false);           if (dfs(start))             size++;     }       return size; }   int main() {     scanf("%d %d", &n, &m);       for (int j = 0; j < m; j++)     {         int no, val;         scanf("%d %d", &no, &val);           adj[no - 1][val - 1] = 1;     }       printf("%d", bipartiteMatch());       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus