(1671) 상어의 저녁식사

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

단계별로 풀어보기

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

 

 

 

이분 그래프에서 헷갈리는 정점 분할 개념인데, 어떤 상어가 다른 상어를 먹을 수 있다면 A그룹에서 간선을 보내고, 먹힐 수 있다면 B그룹에서 간선을 받는다. 같은 상어라도 A그룹은 먹는 쪽, B그룹은 먹히는 쪽으로 역할을 분리했기 때문에 이분 매칭이 된다. 또한 같은 상어가 A그룹에서 B그룹으로 간선을 보내는 경우 및 두 상어의 능력치가 완전히 같은 경우를 주의해야 하는데, 두 상어의 능력치가 같을 때 서로 간선을 보내면 서로 잡아먹는, 문제에서 불가능한 경우로 설정한 상황이 나올 수 있기 때문에 인덱스 등을 기준으로 포식자와 피식자를 구분해야 한다. 또한 한 상어는 상어를 두 마리까지 먹을 수 있으므로 열혈강호 2처럼 A그룹의 간선을 두 배로 불려주면 된다.

 

 

 

#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, cnt= 0;

  cin >> n;
  
  vector<Shark> v(n+1);
  vector<int> A(2*n+1), B(n+1), level(2*n+1);
  vector<vector<int>> adj(2*n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i].STR >> v[i].DEX >> v[i].INT;
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(i>=j && v[i].STR==v[j].STR&&v[i].DEX==v[j].DEX&&v[i].INT==v[j].INT){
        continue;
      }else if(v[i].STR>=v[j].STR&&v[i].DEX>=v[j].DEX&&v[i].INT>=v[j].INT){
        adj[2*i-1].push_back(j);
        adj[2*i].push_back(j);
      }
    }
  }
  
  auto leveling= [&](){
    queue<int> q;
    
    for(int i=1;i<=2*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;
  };
  
  while(1){
    leveling();
    
    int flow= 0;
    
    for(int i=1;i<=2*n;i++){
      if(!A[i]&&matching(matching, i))  flow++;
    }
    
    if(flow)  cnt+= flow;
    else  break;
  }

  cout << n-cnt;

  return 0;
}