(1867) 돌멩이 제거

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

단계별로 풀어보기

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

 

 

 

어떤 돌멩이를 제거하려면 해당 돌멩이가 속한 행이나 열을 달려야 한다. A그룹을 행 노드, B그룹을 열 노드라고 생각하면 돌멩이는 행과 열을 잇는 간선으로 볼 수 있다. 어떤 정점을 선택하면 해당 정점과 인접한 모든 간선(돌멩이)를 제거하는 것으로 볼 수 있다.

어떤 정점 집합에 인접한 간선 집합이 모든 간선의 집합이라면 이 정점 집합을 버텍스 커버라 하고 정점의 수가 최소가 될 때 최소 버텍스 커버라 한다. 이때 쾨니그의 정리에 의해 이분 그래프에서 최소 버텍스 커버의 정점 수는 이분 매칭의 최대 수와 같으므로 이분 매칭 알고리즘을 쓰면 된다.

 

 

 

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

struct Shark {
  int STR;
  int DEX;
  int INT;
};

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

  int n, k, ans;

  cin >> n >> k;
  
  vector<int> A(n+1), B(n+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=0;i<k;i++){
    int r, c;
    
    cin >> r >> c;
    
    adj[r].push_back(c);
  }
  
  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;
}