[11376번] 열혈강호 2

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭

열혈강호(https://www.acmicpc.net/problem/11375) 문제를 응용하여 해결하면 되는 문제이다.

모든 직원이 최대 두 개의 일을 할 수 있는 상황이니 결국 이분 매칭을 두번 하면 된다는 의미다.

즉, 아래 코드에서 dfs를 두번 돌려 aMatch에서 bMatch로 2개의 선이 그어지도록 하면 된다.

이때 visited의 벡터 타입이 열혈강호 문제에서는 bool이었는데 여기서는 int로 변형되었고

최대 2번 방문을 허용하도록 설정하면 끝이난다.

소스 코드 : 

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 80 81 82

#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<int> visited;   bool dfs(int here) {     if (visited[here] > 0)         return false;       visited[here] ++;       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<int>(n, -1);           // 깊이 우선 탐색을 이용해 start에서 시작하는 증가 경로를 찾는다.         if (dfs(start))             size++;            if (dfs(start))             size++;     }       cout << size;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus