소수 쌍


작성일 : 2017-01-21 04:48:10
조회수 : 539



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


i번째 수와 j번째 수를 더하여 소수가 될 때, 이를 i→j로 그래프를 연결시킨다고 생각해 봅니다. 그 다음, 1번째 수와 어느 수가 연결되어 있다면, 카운트 1을 해준 뒤 해당 지점을 방문한 것으로 체크합니다. 그 다음 나머지 점을 기준으로 최대 이분 매칭 알고리즘을 통해 얼마나 매칭되는지 검사합니다.


만약 모든 쌍이 소수가 될 수 있다면 $n$개의 수에 대해 먼저 매칭시켰던 1번째 수와 나머지 수를 제외한 수가 모두 매칭되었으므로 $n-2$개가 매칭됨을 확인할 수 있습니다. 최대 매칭 수가 $n-2$라면 1번째 수와 매칭시켰던 수를 정답으로 추가시킵니다.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int g[50][50],n,l[50],match[50];
bool s[50];
bool isPrime(int n)
{
    for(int i=2; i*i<=n;i++)
        if(n%i==0)return false;
    return true;
}
bool bpm(int u)
{
    for(int v=1;v<n;v++)
    {
        if(g[u][v]&&!s[v]&&!s[u])
        {
            s[v]=true;
            if((match[v]<0)||bpm(match[v]))
            {
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}
int maxBPM(int x)
{
    memset(match,-1,sizeof(match));
    match[0]=match[x]=0;
    int r=0;
    for(int u=1;u<n;u++)
    {
        memset(s,0,sizeof(s));
        s[0]=1;
        if(bpm(u))r++;
    }
    return r;
}
int main()
{
    vector<int> v;
    cin>>n;
    for(int i=0;i<n;i++)cin>>l[i];
    sort(l+1,l+n);
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if(isPrime(l[i]+l[j]))g[i][j]=g[j][i]=1;
    for(int i=0;i<n;i++)
    {
        if(g[0][i])
        {
            int r=maxBPM(i);
            if(r==n-2)v.push_back(l[i]);
        }
    }
    if(!v.size())cout<<"-1";
    else for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
}

소수 쌍 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글