(11375) 열혈강호

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

단계별로 풀어보기

53단계(이분 매칭) 1번째

 

 

 

이분 그래프에서 최대 매칭 수를 찾는 이분 매칭이다. 가장 대중적인 이분 매칭 알고리즘은 포드 풀커슨 알고리즘을 이분 그래프의 특성에 맞게 단순화한 형태이다(Kuhn's algorithm이라고는 하는데 헝가리안 알고리즘으로 불리는 Kukn-Munkres algorithm이 더 유명한지 잘 안 나온다).

DFS를 통해 매칭 수를 늘려 최대 매칭 수를 찾는 알고리즘이다. A그룹의 어떤 정점을 B그룹에 매칭할 때 해당 정점에 매칭된 정점이 없다면 바로 매칭하고, 매칭이 있다면 매칭된 A그룹의 기존 정점을 다른 B그룹의 정점에 매칭할 수 있는지 재귀적으로 확인한다. 시간 복잡도는 O(VE)이다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, m, ans= 0;

  cin >> n >> m;
  
  vector<int> A(n+1), B(m+1);
  vector<vector<int>> adj(n+1);
  vector<bool> visited(n+1);
  
  auto matching= [&](auto self, int x) -> bool {
    visited[x]= true;

    for(int y: adj[x]){
      if(!B[y] || (!visited[B[y]]&&self(self, B[y]))){
        A[x]= y;
        B[y]= x;
        return true;
      }
    }
  
    return false;
  };

  for(int i=1;i<=n;i++){
    int k;
    
    cin >> k;
    
    adj[i].reserve(k);

    for(int j=0;j<k;j++){
      int w;
      
      cin >> w;

      adj[i].push_back(w);
    }
  }
  
  for(int i=1;i<=n;i++){
    if(!A[i]){
      fill(visited.begin(), visited.end(), false);
      
      if(matching(matching, i))  ans++;
    }
  }

  cout << ans;

  return 0;
}

 

 

 

하지만 O(E√V)로 더 뛰어난 호프크로프트-카프 알고리즘이 있다. 위 알고리즘이 포드 풀커슨 알고리즘의 이분 매칭 형태라면 이 알고리즘은 디닉 알고리즘의 이분 매칭 형태라고 볼 수 있다. 처음 배울 땐 디닉이나 호프크로프트-카프가 국내에서는 잘 알려지지 않았었는데 지금은 국내에서도 정보를 나름 많이 찾아볼 수 있게 되었다.

이 알고리즘은 B그룹의 정점에 BFS로 level을 매겨 겹치지 않는 증가 경로를 따라가도록 해 DFS로 매칭할 때 여러 정점을 한 번에, 이미 매칭된 정점은 새로운 정점을 더 빠르게 찾을 수 있게 해준다. 이 과정을 반복하다가 DFS로 더 이상 새로운 매칭이 발생하지 않으면 그때 매칭 수가 최대 매칭 수다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, m, ans= 0;

  cin >> n >> m;
  
  vector<int> A(n+1), B(m+1), level(n+1);
  vector<vector<int>> adj(n+1);
  
  auto leveling= [&](){
    queue<int> q;
    
    for(int i=1;i<=n;i++){
      if(!A[i]){
        level[i]= 0;
        q.push(i);
      }else{
        level[i]= -1;
      }
    }
  
    while(!q.empty()){
      int now= q.front();
      q.pop();
  
      for(int next: adj[now]){
        if(B[next] && level[B[next]]==-1){
          level[B[next]]= level[now]+1;
          q.push(B[next]);
        }
      }
    }
  };
  
  auto matching= [&](auto self, int x) -> bool {
    int now= level[x];
    
    level[x]= -1;

    for(int y: adj[x]){
      if(!B[y] || (level[B[y]]==now+1&&self(self, B[y]))){
        A[x]= y;
        B[y]= x;
        return true;
      }
    }
  
    return false;
  };

  for(int i=1;i<=n;i++){
    int k;
    
    cin >> k;
    
    adj[i].reserve(k);

    for(int j=0;j<k;j++){
      int w;
      
      cin >> w;

      adj[i].push_back(w);
    }
  }
  
  while(1){
    leveling();
    
    int flow= 0;
    
    for(int i=1;i<=n;i++){
      if(!A[i]&&matching(matching, i))  flow++;
    }
    
    if(flow)  ans+= flow;
    else  break;
  }

  cout << ans;

  return 0;
}