글 읽기 - 소수쌍.. 어디서 시간초과가 나는 걸까요?

wyldecat 8년 전 0

arr[0]부터 시작해서 입력을 넣구..

arr[i] (1<=i<=N-1) 과 arr[0]을 더해서 소수라면,

arr[i]와 arr[0] 를 제외한 모든 arr[j]를 벡터에 넣은 뒤,

벡터안에 들어있는 원소들을 홀,짝으로 나눈뒤 가능한 많은 매칭을 찾고,(ford fulkerson 사용했슴당)

매칭수가 충족된다면 arr[i]를 출력하는 식으로 풀었는데요..

시간초과가 나네유.. 혼자 N이 50개인거 넣어봐도 시간안에 나오는것같은데 말입니다 ㅠㅠ

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>

using namespace std;

int N, arr[55];
bool cango[1001][1001],visited[55];
int graph[55][55]={0,};

bool isprime(int x)
{
    for(int i=2;i<=sqrt(x);i++) if(x%i==0) return false;
    return true;
}
bool cmp(const int &a,const int &b){
    return a%2<b%2;
}
bool DFS(int x)
{
    if(x==N-1) return true;
    visited[x]=1;
    for(int i=0;i<N;i++)
    {
        if(graph[x][i]==1 && !visited[i])
        {
            graph[i][x]=1;
            graph[x][i]=0;
            if(DFS(i)) return true;
            graph[x][i]=1;
            graph[i][x]=0;
        }
    }
    visited[x]=0;
    return false;
}
bool check(vector<int> &v)
{
    memset(graph,0,sizeof(graph));
    sort(v.begin(),v.end(),cmp);

    int cntJ=0,sp=0,ep=v.size()+1;
    for(int i=0;i<v.size();i++,cntJ++) if(v[i]%2==1) break;
    if(cntJ!=v.size()-cntJ) return false;
    for(int i=0;i<cntJ;i++) graph[sp][i+1]=1;
    for(int i=cntJ;i<v.size();i++) graph[i+1][ep]=1;
    for(int i=0;i<cntJ;i++){
        for(int j=cntJ;j<v.size();j++)
            if(cango[v[i]][v[j]]) graph[i+1][j+1]=1;
    }

    while(1){
        memset(visited,0,sizeof(visited));
        if(DFS(sp)==false) break;
    }

    for(int i=cntJ;i<v.size();i++) if(!graph[ep][i+1]) return false;
    return true;
}
int main()
{
    freopen("input.txt","r",stdin);
    for(int i=1;i<=1000;i++) for(int j=i+1;j<=1000;j++) if(isprime(i+j)) cango[i][j]=cango[j][i]=true;

    scanf("%d",&N);

    bool chk=0;

    for(int i=0;i<N;i++) scanf("%d",&arr[i]);
    sort(arr+1,arr+N);
    for(int i=1;i<N;i++)
    {
        if(isprime(arr[0]+arr[i])==false) continue;
        vector<int> v;
        for(int j=1;j<N;j++)
        {
            if(i==j) continue;
            v.push_back(arr[j]);
        }
        if(check(v))
        {
            chk=1;
            printf("%d ",arr[i]);
        }
    }
    if(chk==0) printf("-1");
    printf("\n");
    return 0;
}

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

문제

문제

출처

ICPC

소수쌍.. 어디서 시간초과가 나는 걸까요?

wyldecat 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말