글 읽기 - 질문드립니다.

cocogod 7년 전 0

이분매칭을 이용해 이문제를 풀려고 합니다.

첫번째 수를 제외한 모두를 가지고

2개수를 더했을때 소수인지를 저장합니다.

ex) 2번째 3번째 더했는대 소수면 v[2].push(3);

그리고 첫번째수와 더할 수를 빼고 나머지를 가지고 이분매칭을 합니다.

이때 결과가 n-2가 되면 모두가 매칭 되었으므로 출력합니다.

제생각이 틀린건가요??

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int n;
bool prime[2000];
vector<int> v[50];
bool visited[51];
int back[51];

bool dfs(int now,int f){
    if(visited[now] ) return true;
    visited[now] = true;
    
    for(int i=0;i<v[now].size();i++){
        int next = v[now][i];
        if(next == f)
            continue;
        if(back[next] == -1 || dfs(back[next],f))
            return true;
    }
    return false;
}
//f는 첫번째수와 더했으므로 빼고 이분매칭
int solve(int f){
    memset(back,-1,sizeof(back));
    int ret= 0;
    for(int i=1;i<n;i++){
        if(i == f)
            continue;
        memset(visited,false,sizeof(visited));
        if(dfs(i,f))
            ret +=1;
    }
    return ret;
}


int main(){
    memset(prime,true,sizeof(prime));
    //소수 구하기
    for(int i=2;i<=2000;i++){
        if(prime[i]){
            for(int j=i+i;j<=2000;j+=i)
                prime[j] = false;
        }
    }
    
    int data[51];
    scanf("%d",&n); //입력
    for(int i=0;i<n;i++){
        scanf("%d",&data[i]);
    }
    //첫번째를 재외한 나머지수를 2개더해 소수가 되는지 저장
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            if(j == i)
                continue;
            if(prime[data[i] + data[j]])
                v[i].push_back(j);
        }
    }
    
    int ans = 0;
    int flag = 1;
    for(int i=1;i<n;i++){
        //첫번째수와 더해서 소수가 안되면 스킵
        if( !prime[data[0]+data[i]])
            continue;
        //이분매칭 실행 
        if( solve(i) == n-2){ 
            printf("%d ",data[i]);
            flag = 0;
        }
    }
    if(flag)
        printf("-1\n");
}

wowoto9772 7년 전 1

코드는 이분 매칭인듯 이분매칭이 아닌 코드네요. back 선언 하고 안쓰는거 같은데요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문드립니다.

cocogod 7년 전 0

wowoto9772 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말