(3736) System Engineer

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

단계별로 풀어보기

54단계(네크워크 플로우 1) 10번째

 

 

 

디닉 알고리즘의 이분 매칭 형태인 호프크로프트-카프 알고리즘을 써야 한다는 것만 빼면 일반적인 이분 매칭 문제다.

입력 형태가 조금 이상해서 파싱을 해야하는 것만 주의하면 된다.

 

 

 

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

int solve(int n){
  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=1;i<=n;i++){
    string s1, s2;
    
    cin >> s1 >> s2;
    
    int a= stoi(s1.substr(0, s1.length()-1))+1;
    int m= stoi(s2.substr(1, s2.length()-2));
    
    while(m--){
      int b;
      
      cin >> b;
      
      adj[a].push_back(b-n+1);
    }
  }
  
  int ans= 0;
  
  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;
  }

  return ans;
}

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

  int n;
  
  while(cin >> n){
    cout << solve(n) << "\n";
  }

  return 0;
}