Bipartite MatchingPermalink

이분 매칭은 두 그룹간의 각 원소들을 한 번씩만 써서 매칭시켜주는 알고리즘이다.

대개 매칭 수의 최대값을 구하라는 문제가 기본이다.

BOJ 2188 - 축사 배정 문제를 보자.

NN 마리를 축사 MM 에 한 축사에 최대 한마리씩 얼마나 많이 넣을 수 있을지를 구해야 한다. 전형적인 이분 매칭 문제이다.

보통 O(VE)O(VE) 알고리즘이 쓰이고, 더 빠른 알고리즘으론 Dinic 알고리즘처럼 Level Graph 를 구축해 더 빠른 시간에 돌리는 Hopcroft-Karp O(EV)O(E\sqrt V) 알고리즘이 있다.

알고리즘 O(VE)O(VE)Permalink

알고리즘의 기반은 DFS이다. 집합 AABB가 있고 각 원소들이 서로 다른 집합의 원소들과 매칭될 수 있는지 여부를 알 때, 다음과 같이 수행한다.

AA 에 있는 원소 aaBB에 있는 원소와 매칭시킬 수 있는지 판단한다고 하자.

aa 에서 이어져있는 BB 에 있는 원소들을 훑는다고 할때 BB 쪽의 원소 bb 가 아직 AA 에 있는 원소와 매칭이 안되었다면 그것과 매칭시키고 알고리즘을 종료한다.

만약 bbAA 의 원소와 매칭되어있다면, 그 매칭된 원소 aa’bb 가 아닌 다른 원소와 매칭시킬 수 있는지 재귀적으로 살펴본다.

만약 aa’bb 가 아닌 다른 bb’ 와 매칭에 성공한다면 이제 bbaa 랑 매칭시켜줄 수 있다.

만약 모든 bb 에 대해 매칭이 실패한다면 aa 는 어떤 원소와도 매칭시킬 수 없다.

이걸 AA 의 모든 원소에 대해서 수행하고 한 원소 aa 당 DFS를 돌려야 하므로,

시간복잡도는 O(VE)O(VE) 이다. (VV=정점의 개수, EE=간선의 개수)

구현Permalink

struct bipartite {  
   int N, M;  
   vvi edges;  
   vi vis, A, B;  
   bipartite(int N, int M = -1) : N(N), M(~M ? M : N) {  
      edges.resize(N);  
      A.resize(N, -1), B.resize(M, -1), vis.resize(N);  
   }  
   void add_edge(int f, int t) { edges[f].pb(t); }  
   bool dfs(int a) {  
      vis[a] = 1;  
      for (int b: edges[a]) {  
         if (B[b] == -1 || !vis[B[b]] && dfs(B[b])) {  
            A[a] = b, B[b] = a;  
            return 1;  
         }  
      }  
      return 0;  
   }  
   int match() {  
      int ret = 0;  
      for (int i = 0; i < N; i++)  
         fill(all(vis), 0), ret += dfs(i);  
      return ret;  
   }  
};

구현은 간단하다. dfs 함수는 위에서 설명한 동작을 그대로 수행하며 AAaba\to b 로 가는 bb 의 번호를 갖고 있고, BBbab \to a 로 가는 aa 의 번호를 갖고있다.

한 번의 DFS마다 visited\text{visited} 배열을 초기화 시켜줌에 유의한다.

연습 문제Permalink

BOJ 2188 - 축사 배정

BOJ 15271 - 친구 팰린드롬 2

기본 문제이지만, 홀수 정점들과 짝수 정점들에 대한 이분 그래프로 나눈 후 구해주자.

Comments