[11375번] 열혈강호

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

이분 매칭 알고리즘을 이해하고, 접목하면 해결 할 수 있는 간단한 문제이다.

이 문제와 매우 유사한 문제로 축사 배정(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 73 74 75 76 77 78 79

#include <iostream> #include <cstdio> #include <vector>   using namespace std;   int n, m, k;   // adj[i][j] = Ai와 Bj가 연결되어 있는가? bool adj[1001][1001];   // 각 정점에 매칭된 상대 정점의 번호를 지정한다. vector<int> aMatch, bMatch;   // dfs()의 방문 여부 vector<bool> visited;   bool dfs(int here) {     if (visited[here])         return false;       visited[here] = true;       for (int there = 0; there < m; there++)     {         // adj가 존재하면         if (adj[here][there])         {             // bMatch에 아직 매치가 안되있거나,             // 매칭 되어있다면 dfs를 통해 aMatch의 연결 된 것을 재 탐색 시킨다.             if (bMatch[there] == -1 || dfs(bMatch[there]))             {                 aMatch[here] = there;                 bMatch[there] = here;                   return true;             }         }     }     return false; } int main() {     int size = 0;     scanf("%d %d", &n, &m);       for (int i = 0; i < n; i++)     {         scanf("%d", &k);           for (int j = 0; j < k; j++)         {             int pos;             scanf("%d", &pos);               adj[i][pos-1] = 1;         }     }       aMatch = vector<int>(n, -1);     bMatch = vector<int>(m, -1);       for (int start = 0; start < n; start++)     {         visited = vector<bool>(n, false);           // 깊이 우선 탐색을 이용해 start에서 시작하는 증가 경로를 찾는다.         if (dfs(start))             size++;     }       cout << size;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus