(1017) 소수 쌍

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

단계별로 풀어보기

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

 

 

 

2를 제외한 모든 소수는 홀수이고 2는 서로 다른 두 자연수의 합으로 나타낼 방법이 없으므로 항상 짝수+홀수의 합으로 나타난다. 따라서 홀수와 짝수를 A그룹과 B그룹으로 두고 이분 매칭을 하면 된다.

이때 요구하는 정답은 첫 번째 수와 짝지어질 수 있는 수이므로, 첫 번째 수의 간선을 B그룹의 특정 수와 이어지는 하나만 만든 뒤 최대 이분 매칭 수가 A그룹의 정점 수와 같은지 보면 된다. N의 범위는 50이므로 그룹의 간선 수는 많아야 25개이고, 나이브하게 25개의 정점마다 간선을 하나씩만 만들어 이분 매칭을 25번 돌려도 충분히 시간 내에 풀 수 있다.

또한 애초에 A그룹과 B그룹의 수가 다르면 볼 것도 없이 불가능이다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 2000

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  bool soe[MAX+1]= {true, true, false, };
  
  for(int i=4;i<=MAX;i+=2)  soe[i]= true;
  for(int i=3;i*i<=MAX;i+=2){
    if(soe[i])  continue;
    
    for(int j=i;i*j<=MAX;j+=2)  soe[i*j]= true; 
  }

  int n, first= 0;

  cin >> n >> first;
  
  vector<int> Anum(1), Bnum(1), A(n/2+1), B(n/2+1), level(n/2+1);
  vector<vector<int>> adj(n/2+1);
  
  Anum.push_back(first);
  for(int i=1;i<n;i++){
    int x;
    
    cin >> x;
    
    if((x&1)==(first&1))  Anum.push_back(x);
    else  Bnum.push_back(x);
  }
  
  if(Anum.size()!=1+n/2 || Bnum.size()!=1+n/2){
    cout << -1;
    
    return 0;
  }
  
  for(int i=1;i<Anum.size();i++){
    for(int j=1;j<Bnum.size();j++){
      if(!soe[Anum[i]+Bnum[j]])  adj[i].push_back(j);
    }
  }
  
  auto leveling= [&](){
    queue<int> q;
    
    for(int i=1;i<=n/2;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;
  };

  vector<int> cand= adj[1], ans;
  
  for(int elem:cand){
    adj[1]= vector<int> { elem };
    fill(A.begin(), A.end(), 0);
    fill(B.begin(), B.end(), 0);
    
    int cnt= 0;
    
    while(1){
      leveling();
      
      int flow= 0;
      
      for(int i=1;i<=n/2;i++){
        if(!A[i]&&matching(matching, i))  flow++;
      }
      
      if(flow)  cnt+= flow;
      else  break;
    }
    
    if(cnt==n/2)  ans.push_back(Bnum[elem]);
  }
  
  if(ans.empty()){
    cout << -1;
    
    return 0;
  }
  
  sort(ans.begin(), ans.end());
  
  for(int elem:ans)  cout << elem << " ";

  return 0;
}