글 읽기 - 구현부분 좀 알려주세요

didwlvv 7년 전 0

저는 일단 네트워크 플로우로 작성을 해봤습니다.

일단 홀수,짝수를 나눴고 홀수에서 짝수로 연결을 시켰습니다. 그런데 지금 첫번째하고 연결된 걸 저장해놓고 뽑아내라는데 일단 그 수를 고정시켜서 비교하는 법을 모르겠습니다. 플로우는 계속 유동적으로 바뀌는데 예시에서 보면 1-4를 연결시키는데 이걸 어떻게 고정시켜놓고 나머지를 연결시키나 구현을 못하겠습니다. 이부분을 알려주시면 감사하겠습니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;
vector<int>v[2005];
int n,sink, source,idx,aidx,bidx;
int ss[1000];   int chk[2001];  int a[51];  int b[51];
int capacity[2005][2005];   int flow[2005][2005];   int p[2005];
void init(); void solve();

int main(){
    init();
    solve();
    
    return 0;
}

void init(){
    for(int i=2; i<2001; i++){  //소수 구하기
        if(chk[i]==0){
            chk[i]=1;
            ss[idx++]= i;
            for(int j=i*2; j<2001; j+=i){
                chk[j]=1;
            }
        }
    }
    
    scanf("%d", &n);
   
    for(int i=0; i<n; i++){
        int t;
        scanf("%d", &t);
        if(t%2==0){
            b[bidx++]=t;    //짝수
        }
        else{
            a[aidx++]=t;    //홀수
        }
    }
    
    
    for(int i=0; i<aidx; i++){
        for(int j=0; j<bidx; j++){
            v[a[i]].push_back(b[j]);
            v[b[j]].push_back(a[i]);
            capacity[a[i]][b[j]]=1;
        }
    }
    for(int i=0; i<aidx; i++){
        v[0].push_back(a[i]);
        v[a[i]].push_back(0);
        capacity[0][a[i]]=1;
    }
    for(int i=0; i<bidx; i++){
        v[b[i]].push_back(2001);
        v[2001].push_back(b[i]);
        capacity[b[i]][2001]=1;
    }
    

}

void solve(){
    if(aidx !=bidx){
        cout <<"-1"<<endl;
        return;
    }
    int num1=0,num2=0;
    sink =2001;
    int res=0;
    
    while(1){
        queue<int>q;
        memset(p,-1,sizeof p);
        p[0]=0;
        q.push(0);
        
        while(!q.empty() && p[sink] == -1){
            int now = q.front();    q.pop();
            
            for(int i=0; i<v[now].size(); i++){
                int next = v[now][i];
                int t= now+next;
                
                if(capacity[now][next] - flow[now][next] >0 && p[next] ==-1){
                    bool ok =false;
                    for(int j=0; j<idx; j++){
                        if(t == ss[j]){
                            ok=true;
                            break;
                        }
                        if(t < ss[j])break;
                    }
                    
                    if(!ok)continue;
                    
                    
                    p[next]=now;
                    q.push(next);
                }
            }
        }
        
        if(p[sink]==-1)break;
        
       
        
        for(int i=sink; i!=source; i=p[i] ){
            flow[p[i]][i] +=1;
            flow[i][p[i]] -=1;
        }
        
        res +=1;
        
        
    }
    
}

ehddml3 7년 전 0

1-4 연결 후 1,4 제외하고 플로우 돌리기

didwlvv 7년 전 0

그러면 1-4를 연결할 때는 플로우를 안돌리고 1하고 하나를 연결시킨다음에 플로우 한번 돌리나요??

ehddml3 7년 전 0

넹 저는 그렇게 했어요. if(prime[num[0]+num[i]]) 상태면 둘이 연결짓고 그다음에 0과 i가 아닌 애들끼리만 플로우 돌렸어요. 나머지들이 전부 매칭이 되면 정답에 추가해주는식으로

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

문제

문제

출처

ICPC

구현부분 좀 알려주세요

didwlvv 7년 전 0

ehddml3 7년 전 0

didwlvv 7년 전 0

ehddml3 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말