2 분 그림 의 최대 일치 - 일치 하 는 문제 해결

제목 설명
제목 설명 이 만약 에 두 개의 정수 와 소수 라면 이 두 정 수 는 '소수 동반자' 라 고 부른다. 예 를 들 어 2 와 5, 6 과 13 은 통신 암호 화 에 응용 할 수 있다.현재 암호 학 회 는 기 존의 N (N 은 짝수) 개의 정수 중에서 몇 쌍 을 골 라 서 '소수 배우자' 를 구성 하 는 프로그램 을 설계 하 십시오. 예 를 들 어 4 개의 정수 가 있 습 니 다. 2, 5, 6, 13. 5 와 6 을 한 그룹 으로 나 누 면 '소수 배우자' 만 얻 을 수 있 고 2 와 5, 6 과 13 을 두 그룹 으로 나 누 면 '소수 배우자' 를 얻 을 수 있 습 니 다.'소수 배우자' 가 가장 많은 방안 을 '최선 의 방안' 이 라 고 한다. 물론 암호 학 회 는 '최선 의 방안' 을 찾 아 달라 고 한다.
입력:
정 짝수 N (N ≤ 100) 이 있 는데 선택 할 자연수 의 개 수 를 나타 낸다. 뒤에 구체 적 인 숫자 를 제시 하고 범 위 는 [2, 30000] 이다.
출력:
정수 K 를 출력 하면 '최선 의 방안' 이 '소수 동반자' 의 대 수 를 구성 하 는 것 을 나타 낸다.
 
입력 설명:
입력 설명 1 짝수 n 2 입력 정수 n 개 입력
출력 설명:

구 하 는 '최선 의 방안' 은 '소수 동반자' 의 대 수 를 구성한다.
예시 1
입력
복제 하 다.

4
2 5 6 13

출력
복제 하 다.

2

 
 
 
 
[문제 분석]:
주어진 숫자 에서 두 개의 수 를 취하 고 이 두 개의 수 는 만족 소수 와 일치 하 며 하 나 를 완성 하면 쉽게 알 수 있 습 니 다. 그 중 하 나 는 짝수 이 고 다른 하 나 는 홀수 입 니 다.
(그렇지 않 으 면 짝수 와 소수 가 될 수 없다)
따라서 원래 의 수 를 두 부분 으로 나 누 었 는데, 그 중 일 부 는 홀수 이 고, 다른 일 부 는 짝수 이다.
원래 문 제 는 '홀수, 짝수' 에서 의 연결 (연결 조건 은 소수) 을 완성 하여 최종 적 으로 일치 하 는 총 수 를 가장 많이 합 니 다.
 
이 문 제 는 2 분 그림 의 최대 일치 이 며, 2 분 그림 에는 두 부분 점 이 포함 되 어 있 으 며, 각 점 은 다른 부분 점 의 부분 과 만 연 결 될 수 있다.
두 부분 중 몇 가지 점, 즉 두 쌍 을 연결 하여 최대 일치 수 를 구하 십시오.
 
헝가리 알고리즘:
 
점 을 상하 두 부분 으로 나 누 어 홀수 arr 1 []  화해시키다   짝수 arr2 []
매 라운드 위의 점 U 를 고찰 하 다.   아래 점 을 옮 겨 다 니 며 그 중 하나 에 대해 V  (u, v) 일치 할 수 있 고 (예 를 들 어 소수 로 조합) 이번 라운드 에 접근 하지 않 았 습 니 다.

그러면 v 점 이 일치 하 는 지 판단 하고 그렇지 않 으 면 직접 일치 합 니 다

v 점 전에 일치 한 적 이 있다 면 (match [v]! = - 1) v 점 은 match [v] (즉, match [v] 점 에서 다른 일치 하 는 점 을 찾 을 수 있 음) 성공 하면 바로 포기 합 니 다

 
논리 구현:

bool find(int u)  //   u                
{
    for (int v = 0; v < N; v++)
    {
        //u v                      v     （        ）
        if (map[u][v] && !visit[v])
        {
            visit[v] = true;
            // v      （=-1）               v       
            if (match[v] == -1 || find(match[v]))
            {

              
                match[v] = u;  //      
                return true;
            }


        }
    }
  
    return false;

}

관건 은 틀 리 기 쉽다.
visit 배열 의 이 해 는 모든 라운드 에서 false 로 초기 화 되 어야 합 니 다.  한 라 운 드 는 하나의 기수 로 일치 하 는 것 으로 이해 할 수 있 습 니 다.
또 다른 실현 은 소수 의 판단 이다.
모든 정 수 는 6i 6i + 1 6i + 2 6i + 3 6i + 4 6i + 5 로 나 눌 수 있다.
우선 6i 6i + 2 6i + 3 6i + 4 의 유형 수 는 반드시 소수 가 아 닙 니 다. 2 또는 3 으로 나 눌 수 있 기 때 문 입 니 다.
그래서 하나의 숫자 를 만족 시 킬 수 밖 에 없어 요. num.  그 num% 6 = = 1 또는  num% 6 = = 5 가 소수 일 수 있 음
다음은 i = 2 에서 i = sqrt (num) 로 순환 합 니 다.  i 인지 아 닌 지 를 판단 하 는 것 은 num 에 의 해 제 거 될 수 없다.
한층 더 최적화:
그 중 일부 i 는 판단 할 필요 가 없다. 이런 i 는 6k 6k + 2 6k + 3 6k + 4 를 만족시킨다.  
반증 법, 만약 에 이런 i 가 num 에 의 해 정 제 될 수 있다 면 num 도 6k 6k + 2 6k + 3 6k + 4 를 만족 시 킬 것 이다. 이것 은 num 이 반드시 6k + 1 또는 6k + 5 와 부합 되 지 않 을 것 이다.

bool isPrime(int num)
{

    int data = num;
    int loopNum = sqrt(num);
    for (int i = 2; i <= loopNum; i++)
    {
        if (data % i == 0)
        {
            return 0;
        }
    }
    return 1;

    if (num < 4)
        return num > 1;


    //           6i 6i+1 6i+2 6i+3 6i+4 6i+5   
    //       6i+1 6i+5     
    if (num % 6 != 1 && num % 6 != 5)
        return false;

    //       i=2 i=sqrt(Num)    Num  
    //            6i+2 6i+3 6i+4 6i     ：  num  6i      num 6      num=6i+1 6i+5   


    for (int i = 5; i < sqrt(num); i += 6)
    {
        if (num % (i) == 0 || num % (i + 2) == 0)
            return false;
    }

    return true;

}

 
최대 일치 수 를 어떻게 통계 합 니까?
즉, 모든 홀수 에 대해 find () 를 호출 하면 true 로 돌아 갑 니 다.  그럼 count + +
매 라운드 가 끝나 면 visit = {false} 을 초기 화 합 니 다.
 
 
전체 코드:

#include
#include
#include
#include
#include
using namespace std;
int M, N;
bool visit[100] = { false };//                 
int arr1[100] = { -1 };//  
int arr2[100] = { -1 };//  
bool map[100][100] = { false };//map[i][j]      i      j      
int match[100];//match[j]   j         


bool isPrime(int num)
{

    int data = num;
    int loopNum = sqrt(num);
    for (int i = 2; i <= loopNum; i++)
    {
        if (data % i == 0)
        {
            return 0;
        }
    }
    return 1;

    if (num < 4)
        return num > 1;


    //           6i 6i+1 6i+2 6i+3 6i+4 6i+5   
    //       6i+1 6i+5     
    if (num % 6 != 1 && num % 6 != 5)
        return false;

    //       i=2 i=sqrt(Num)    Num  
    //            6i+2 6i+3 6i+4 6i     ：  num  6i      num 6      num=6i+1 6i+5   


    for (int i = 5; i < sqrt(num); i += 6)
    {
        if (num % (i) == 0 || num % (i + 2) == 0)
            return false;
    }

    return true;





}



bool find(int u)  //   u                
{
    for (int v = 0; v < N; v++)
    {
        //u v                      v     （        ）
        if (map[u][v] && !visit[v])
        {

           
            visit[v] = true;
            // v      （=-1）               v       
            if (match[v] == -1 || find(match[v]))
            {

               
                match[v] = u;  //      
                return true;
            }


        }
    }
    return false;

}





int main()
{
    int num;
    cin >> num;



    for (int i = 0; i < num; i++)
    {
        int tmp;
        cin >> tmp;
        if ((tmp & 1) == 1)  //  
        {
            arr1[M++] = tmp;
        }
        else  //  
        {
            arr2[N++] = tmp;
        }

    }

    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
        {
            if (isPrime(arr1[i] + arr2[j]))  //    
                map[i][j] = true;//      
          
        }

    for (int i = 0; i < N; i++)
        match[i] = -1;


    int count = 0;
    for (int i = 0; i < M; i++)
    {
        //            i       ，
        //                           visit=false;
        for (int j = 0; j < N; j++)
            visit[j] = false;
        if (find(i))
            count++;
    }
    cout << count << endl;
}